정렬 알고리즘(선택 정렬/버블 정렬/삽입 정렬) (파이썬 코드)

1. 선택정렬 (selection sort)

 

최소값을 찾아서 맨 앞으로 보내는 방식으로 정렬하는 방법이다.


시간복잡도
O(n^2)
 

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

 

---

 
2. 버블정렬(bubble sort)

현재 배열 요소와 그 다음 배열 요소를 비교하여 조건에 맞으면 교환하는 정렬
안정적인 정렬방법이다.

시간복잡도
O(n^2)

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

 

 

---

 

 

3. 삽입정렬(insertion sort)

삽입 정렬은 배열의 모든 요소를 순회하면서 각 요소를 이미 정렬된 부분 배열에 적절한 위치에 삽입하는 방식으로 동작한다.

이미 거의 정렬되어 있는 배열에서 효율적인 정렬방법이다.

 

시간복잡도
O(n^2)

def insertion_sort(array):
    for i in range(1, len(array)):
        j = i - 1
        key = array[i]
        while j >= 0 and key < array[j]:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = key
    return array