버블/선택/삽입 정렬은 느리다. 마치 거북이 같다. 퀵 정렬은 평균적으로 빠르지만 최악의 경우 느려진다. 음... 토북이라고 하자.

정렬	설명	시간복잡도	공간복잡도	안정성
버블 정렬	이웃한 두 원소를 비교 및 교환	$O(N^2)$	$O(1)$	O
선택 정렬	제일 작은 원소를 맨 앞 원소와 교환	$O(N^2)$	$O(1)$	X
삽입 정렬	원소를 이미 정렬된 원소들 속에 삽입	$O(N^2)$ 거의 정렬된 배열: $O(N)$ 근접	$O(1)$	O
퀵 정렬	피벗 기준으로 더 작은 / 큰 값으로 나누며 정렬	평균 $O(N\log N)$ 최악 $O(N^2)$	평균 $O(\log N)$ 최악 $O(N)$	X

정렬 알고리즘

• 원소를 대소 관계에 따라 일정한 순서로 바꾸는 알고리즘
• 안정적 정렬
  • 안정적인 정렬: 동일한 원소의 순서가 정렬 후 유지됨
  • 안정적이지 않은 정렬: 동일한 원소의 순서가 유지되지 않음

버블 정렬

• 아직 정렬되지 않은 부분에서 이웃한 두 원소를 비교하고, 필요하면 교환
• 매번 가장 작은 원소가 맨 앞으로 이동함

def bubble_sort(a):
    N = len(a)

    for i in range(N - 1):
        # 앞쪽 i개 원소까지는 정렬됐고, a[i]부터 정렬되지 않음
        for j in range(N - 1, i, -1):
            # 앞뒤 원소 값을 비교하여, 앞쪽 값이 더 크면 교환
            if a[j - 1] > a[j]:
                a[j - 1], a[j] = a[j], a[j - 1]

arr = [6, 4, 3, 7, 1, 9, 8]
bubble_sort(arr)
print(arr)  # [1, 3, 4, 6, 7, 8, 9]

• 시간 복잡도: $(N - 1) + (N - 2) + ... + 1 = \frac{N(N-1)}{2}$ -> $O(N^2)$
• 공간 복잡도: 내부에서 새로운 배열을 만들지 않고, 기존 배열의 값만 바꿈 -> $O(1)$
  • 🤔 배열의 길이가 $N$이면 그만큼 공간이 필요하니 $O(N)$ 아닌가요?
  • 😾 함수의 공간 복잡도를 계산할 때는, 매개변수로 전달된 외부 데이터의 크기는 고려하지 않습니다.
• 서로 떨어져 있는 원소를 교환하지 않으므로, 값이 동일한 원소의 순서가 유지됨 -> 안정적

선택 정렬

• 아직 정렬되지 않은 부분에서 값이 가장 적은 원소 a[min] 선택
• a[min]과 아직 정렬되지 않은 부분의 맨 앞 원소를 교환

def selection_sort(a):
    N = len(a)
    for i in range(N - 1):
        # 정렬되지 않은 부분에서 가장 작은 원소의 인덱스
        min_idx = i
        for j in range(i + 1, N):
            if a[j] < a[min_idx]:
                min_idx = j

        # 정렬되지 않은 부분에서, 맨 앞 원소와 최솟값 원소 교환
        a[i], a[min_idx] = a[min_idx], a[i]

arr = [6, 4, 8, 3, 1, 9, 7]
selection_sort(arr)
print(arr)  # [1, 3, 4, 6, 7, 8, 9]

• 시간 복잡도: $(N - 1) + (N - 2) + ... + 1 = \frac{N(N - 1)}{2}$ -> $O(N^2)$

• 공간 복잡도: 내부에서 새로운 배열을 만들지 않고, 기존 배열의 값만 바꿈 -> $O(1)$
  

• 서로 이웃하지 않은 원소를 교환하므로, 안정적이지 않음

  • 위 예제에서 정렬이 완료됐을 때, 뒤에 있던 3B가 3A보다 앞에 정렬된 것을 확인할 수 있음

삽입 정렬

• 아직 정렬되지 않은 부분의 맨 앞 원소를, 정렬된 부분의 알맞은 위치에 삽입

def insertion_sort(a):
    N = len(a)
    for i in range(1, N):
        j = i
        temp = a[i]

        # 1. 배열의 왼쪽 끝에 도달할 때까지
        # 2. 이웃한 왼쪽 원소가 temp보다 작거나 같을 때까지
        # 아래 과정을 반복
        while j > 0 and a[j - 1] > temp:
            a[j] = a[j - 1]     # 이웃한 왼쪽 원소를 현 위치에 대입
            j -= 1
        a[j] = temp             # 멈춘 위치에 temp를 대입

arr = [6, 4, 1, 7, 3, 9, 8]
insertion_sort(arr)
print(arr)  # [1, 3, 4, 6, 7, 8, 9]

• 시간 복잡도: $(N - 1) + (N - 2) + ... + 2 + 1 = \frac{N(N - 1)}{2}$ -> $O(N^2)$
• 공간 복잡도: 내부에서 새로운 배열을 만들지 않고, 기존 배열의 값만 바꿈 -> $O(1)$
• 서로 떨어져 있는 원소를 교환하지 않으므로, 값이 동일한 원소의 순서가 유지됨 -> 안정적
• 이미 거의 정렬된 배열의 경우, 삽입 과정에서 탐색을 그만큼 덜 하게 되므로 빠름
  • 안쪽 반복문의 실행 횟수가 줄어들기 때문에 $O(N)$에 근접

퀵 정렬

• 일반적으로 사용되는 아주 빠른 정렬 알고리즘
• 각 배열에서 피벗을 선택하여, 이를 기준으로 두 부분배열로 나누기를 재귀적으로 반복
• 모든 부분배열에 원소가 1씩 남으면 정렬이 완료됨

퀵 정렬 과정

• 준비 과정
  • 배열의 첫 인덱스를 start, 끝 인덱스를 end로 둠
  • 포인터 l를 start 위치에, r를 end 위치에 둠
    • cf. 포인터는 배열의 특정 원소 위치를 가리키는 인덱스로, C언어의 포인터가 아님
  • 임의의 pivot 값을 설정함 (여기선 중앙값)

• 두 그룹으로 나누기
  • a[l] >= pivot인 원소를 찾을 때까지 l을 오른쪽으로 이동
  • a[r] <= pivot인 원소를 찾을 때까지 r를 왼쪽으로 이동
  • l와 r가 모두 정지한 경우
    • a[l]와 a[r] 값을 교환 (두 값이 동일해도 교환)
    • l를 1 증가, r를 1 감소
  • l와 r가 교차할 때까지 반복

• 재귀적으로 나누기
  • start <= r일 경우, a[0]부터 a[r]까지 왼쪽 부분배열도 재귀 호출로 정렬
    • 위 부분배열엔 피벗 이하의 값이 담김
  • l <= end일 때, a[l] 부터 a[end]까지 오른쪽 부분배열도 재귀 호출로 정렬
    • 위 부분배열엔 피벗 이상의 값이 담김
  • l > r + 1일 때 정지한 경우 a[r]와 a[l] 사이에 원소가 있을 때도 있음
    • 해당 원소는 피벗과 값이 동일하므로, 그냥 놔두면 됨

def quick_sort(a, start, end):
    l = start                    # 왼쪽 인덱스
    r = end                     # 오른쪽 인덱스
    pivot = a[(l + r) // 2]  # 피벗

    print(f"a[{start}] ~ a[{end}]: {a[start:end + 1]}")

    # 배열을 두 그룹으로 나누기
    while l <= r:
        while a[l] < pivot: l += 1
        while a[r] > pivot: r -= 1
        if l <= r:
            a[l], a[r] = a[r], a[l]
            # a[l] 혹은 a[r]과 pivot의 값이 동일할 때
            # 탈출하기 위한 용도
            l += 1
            r -= 1

    # 왼쪽 그룹을 나누기
    if start < r:
        quick_sort(a, start, r)
    # 오른쪽 그룹을 나누기
    if l < end:
        quick_sort(a, l, end)

a = [5, 8, 4, 2, 6, 1, 3, 9, 7]
quick_sort(a, 0, len(a) - 1)
print(a)    # [1, 2, 3, 4, 5, 6, 7, 8, 9]

• 퀵 정렬에선 서로 이웃하지 않는 원소가 교환되므로, 안정적이지 않음

피벗 선택하기

• 빠른 정렬을 위해선 배열의 중앙값을 선택하는 것이 이상적
• 하지만 중앙값을 구할 때 필요한 계산 시간을 고려하면, 피벗을 선택하는 의미가 없어짐
• 배열의 원소가 3개 이상일 땐 아래와 같은 방법 사용 가능
  • (1) 배열의 맨 앞, 가운데, 맨 끝 원소를 정렬
  • (2) 가운데 원소와 맨 끝에서 두번째 원소를 교환
  • (3) a[end - 1]을 피벗으로 선택
  • (4) l의 시작위치를 start + 1로, r의 시작 위치를 end - 1로 이동한 후 스캔
  • (5) 이후 부분배열도 재귀적으로 정렬

최종 알고리즘

• 퀵 정렬은 원소 수가 적은 경우 비효율적
• 앞선 피벗 선택법을 적용하되, 원소 수가 9개 이하면 삽입 정렬로 대체

def sort3(a, idx1, idx2, idx3):
    # 피벗 정하기 전 원소 3개 정렬
    if a[idx1] > a[idx2]: a[idx1], a[idx2] = a[idx2], a[idx1]
    if a[idx2] > a[idx3]: a[idx2], a[idx3] = a[idx3], a[idx2]
    if a[idx1] > a[idx2]: a[idx1], a[idx2] = a[idx2], a[idx1]
    return idx2     # 가운데 원소

def insertion_sort(a, start, end):
    # 삽입 정렬
    for i in range(start + 1, end + 1):
        j = i
        temp = a[i]
        while j > start and a[j-1] > temp:
            a[j] = a[j-1]
            j -= 1
        a[j] = temp

def quick_sort(a, start, end):
    if (end - start + 1) <= 9:
        insertion_sort(a, start, end)
    else:
        l = start
        r = end

        # 첫, 가운데, 끝 원소를 정렬
        mid = sort3(a, l, (l + r) // 2, r)
        pivot = a[mid]  # 가운데 원소의 값을 피벗으로 설정

        # 가운데 원소와, 끝에서 2번째 원소 교환
        a[mid], a[r - 1] = a[r - 1], a[mid]

        # left를 우측 1칸, right를 좌측 2칸 이동
        l += 1
        r -= 2

        # 이후 과정은 기존 알고리즘과 동일
        while l <= r:
            while a[l] < pivot: l += 1
            while a[r] > pivot: r -= 1
            if l <= r:
                a[l], a[r] = a[r], a[l]
                l += 1
                r -= 1

        if start < r: quick_sort(a, start, r)
        if l < end: quick_sort(a, l, end)

a = [5, 8, 4, 2, 6, 1, 3, 9, 7, 0, 3, 5]
quick_sort(a, 0, len(a) - 1)
print(a)

시간 복잡도

• 배열을 반씩 나누어 작은 문제를 푸는 과정을 반복
• 배열의 길이가 $N$일 때, 평균적으로 $O(N \log N)$
  • 피벗 기준으로 배열이 균등하게 나뉘어지는 경우 (두 부분개열의 수가 비슷), 보통 $\log_2(N)$번 나누게 됨 -> $O(\log N)$
  • 각 단계에서 전체 데이터를 1번씩 확인하므로, $O(N)$의 시간 소요
  • 총 $O(N \log N)$
• 단, 배열이 균등하지 않은 최악의 경우 $O(N^2)$
  • 예: 매번 1개의 원소와 나머지 원소로 나누어질 때
  • 총 $N$단계를 거쳐야만, 모든 부분배열의 원소가 1개만 남게 됨

공간 복잡도

• 내부에서 새로운 배열을 만들지 않고, 기존 배열의 값만 바꿈 -> $O(1)$
• 최대 재귀 깊이만큼 함수 호출 정보를 저장할 공간 필요 -> 평균 $O(\log N)$, 최악 $O(N)$
  • 🤔 함수 내에서 재귀 호출이 2회 이루어지는 만큼, 실제 함수 호출 횟수는 $\log N$번보다 많지 않나요?
  • 😾 공간 복잡도를 계산할 땐 최대 재귀 깊이를 반영하지, 총 재귀 횟수를 반영하지 않습니다. 먼저 호출된 함수가 종료되어야 두 번째 호출이 실행되므로, 두 호출이 같은 시점에 동시에 메모리에 남아 있지 않습니다. 따라서 재귀 호출을 하면서 쌓이는 최대 깊이 $\log N$이 기준이 됩니다.
• 최종 공간 복잡도: 평균 $O(log N)$, 최악 $O(N)$