정렬 알고리즘

기본 정렬 알고리즘 정리.

버블 정렬 — O(n²)

인접한 두 원소를 비교하며 swap한다. 단순하지만 느리다.

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

퀵 정렬 — 평균 O(n log n)

피벗 기준 분할 정복. 평균적으로 빠르나 최악 O(n²).

fn quick_sort(arr: &mut Vec<i32>, low: usize, high: usize) {
    if low < high {
        let pivot = partition(arr, low, high);
        if pivot > 0 { quick_sort(arr, low, pivot - 1); }
        quick_sort(arr, pivot + 1, high);
    }
}

비교표

알고리즘	평균	최악	공간
버블	O(n²)	O(n²)	O(1)
퀵	O(n log n)	O(n²)	O(log n)
병합	O(n log n)	O(n log n)	O(n)