정렬 알고리즘 모음 (파이썬)

이코테 정렬 참고

• 선택 정렬

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

- O(n^2)

• 삽입 정렬

def insertion_sort(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
            else:
                break
    return arr

- O(n^2)
- 데이터가 거의 정렬되어 있을 때 best

• 퀵 정렬 (pythonic method)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    tail = arr[1:]

    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

- O(log n)
- 반대로 데이터가 거의 정렬되어 있을 때 worst: O(n^2)

• 계수 정렬

count = [0] * (max(arr) + 1)
for a in arr:
	count[a] += 1

- O(N+K) (K = 데이터 중 최댓값의 크기)
- 데이터가 한정된 범위 내에 있고, 동일한 값을 가지는 데이터가 여러개 등장할 때