이름·특징 한눈에 보기

기본 비교 기반 정렬

버블 정렬 (Bubble Sort)

인접한 두 원소를 비교하며 큰 값을 오른쪽으로 버블처럼 떠오르게 교환합니다. 한 번 순회할 때마다 가장 큰 값이 끝으로 이동하며, n-1번 반복하면 정렬 완료. 시간복잡도는 최선/평균/최악 모두 $O(n^2)$로 비효율적이지만 구현이 가장 쉽습니다.

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

선택 정렬 (Selection Sort)

매번 배열에서 최소값을 찾아 맨 앞부터 순서대로 교환합니다. i번째 위치부터 끝까지 최소값 검색 후 교환하는 식으로 n-1번 반복. 교환 횟수는 적지만(최대 n-1회) 비교가 $O(n^2)$라 느리고, 불안정 정렬입니다.

pythondef 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]

삽입 정렬 (Insertion Sort)

왼쪽부터 이미 정렬된 부분 배열을 만들며, 새 원소를 적절한 위치에 삽입합니다. 카드 놀이처럼 한 장씩 끼워넣는 방식으로, 거의 정렬된 데이터에서 최선 $O(n)$을 보입니다. 평균 $O(n^2)$지만 안정적이고 적은 데이터에 적합합니다.

pythondef insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        for j in range(i, 0, -1):
            if arr[j - 1] > arr[j]:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
            else:
                break

고급 비교 기반 정렬

병합 정렬 (Merge Sort)

분할정복으로 배열을 반씩 쪼개 각각 재귀 정렬 후 병합합니다. 작은 배열 두 개를 정렬된 채 합치는 merge 과정이 핵심이며, 항상 $O(n \log n)$으로 안정적입니다. 하지만 $O(n)$ 추가 메모리가 필요합니다.

pythondef merge_sort(arr):
    if len(arr) < 2:
        return arr
    mid = len(arr) // 2
    low = merge_sort(arr[:mid])
    high = merge_sort(arr[mid:])
    merged = []
    i = j = 0
    while i < len(low) and j < len(high):
        if low[i] < high[j]:
            merged.append(low[i])
            i += 1
        else:
            merged.append(high[j])
            j += 1
    merged += low[i:]
    merged += high[j:]
    for k in range(len(arr)):
        arr[k] = merged[k]

퀵 정렬 (Quick Sort)

피벗(보통 첫/마지막 원소)을 선택해 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할한 뒤 재귀합니다. 평균 $O(n \log n)$으로 실무 최강이지만 피벗 선택에 따라 최악 $O(n^2)$ 발생 가능하며 불안정합니다.

pythondef quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = len(arr) // 2
    left = [x for x in arr if x < arr[pivot]]
    mid = [x for x in arr if x == arr[pivot]]
    right = [x for x in arr if x > arr[pivot]]
    arr[:] = quick_sort(left) + mid + quick_sort(right)

힙 정렬 (Heap Sort)

최대 힙(부모 > 자식)을 구성한 뒤 최대값을 끝으로 옮기고 힙을 재구성하며 반복합니다. 힙 빌드 $O(n)$, 추출 $O(\log n)$로 항상 $O(n \log n)$이며 in-place(추가 메모리 거의 없음)이지만 불안정하고 상수배가 큽니다.

pythondef heap_sort(arr):
    def heapify(n, i):
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and arr[l] > arr[largest]:
            largest = l
        if r < n and arr[r] > arr[largest]:
            largest = r
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(n, largest)
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(i, 0)

셸 정렬 (Shell Sort)

삽입 정렬을 큰 간격(h)부터 점점 줄여가며 적용합니다. h= n/2, n/4...1로 줄이며, 삽입 정렬의 일반화로 평균 $O(n^{4/3})$ ~ $O(n^{3/2})$ 정도. 간격 선택에 따라 성능 차이 큽니다.

pythondef shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2

논비교 정렬

기수 정렬 (Radix Sort)

숫자의 각 자릿수(일의 자리→십의 자리 등)를 기준으로 안정 정렬(보통 카운팅 정렬 사용) 반복합니다. 비교 없이 안정적이며 $O(d(n + k))$ (d=자릿수, k=진수)지만 정수/고정 길이 데이터에만 적합합니다.

pythondef radix_sort(arr):
    from collections import deque
    max_num = max(arr)
    exp = 1
    while max_num >= exp:
        buckets = [deque() for _ in range(10)]
        for num in arr:
            buckets[(num // exp) % 10].append(num)
        idx = 0
        for bucket in buckets:
            while bucket:
                arr[idx] = bucket.popleft()
                idx += 1
        exp *= 10

카운팅 정렬 (Counting Sort)

값 범위 0~k의 각 값 빈도를 세어 누적합으로 위치 계산합니다. $O(n + k)$로 매우 빠르지만 k가 클 경우 메모리 과다 사용, 범위가 작을 때만 실용적이며 안정 정렬입니다.

pythondef counting_sort(arr):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        count[num] += 1
    idx = 0
    for i in range(len(count)):
        while count[i] > 0:
            arr[idx] = i
            idx += 1
            count[i] -= 1