[Algorithm] 정렬 알고리즘 알아보기

다양한 정렬 알고리즘을 정리하기 위해 작성했습니다.

거픔정렬 (Bubble Sort)

거품정렬은 인접한 두 수의 크기를 비교하고, 조건에 맞지 않다면 자리를 버꾸며 정렬하는 알고리즘 입니다.

정렬 과정 (오름차순)

        
      
for i in range(n):
    for j in range(1, n - i):
        if data[j - 1] > data[j]:
            data[j], data[j - 1] =\
             data[j - 1], data[j]

인접한 두 원소의 대소비교 후, 왼쪽 원소가 더 크다면 두 원소의 자리를 바꿉니다. 이 과정을 리스트 마지막까지 반복합니다. 최종적으로 맨 마지막 자리에는 가장 큰 원소가 오게됩니다.
이번에는 맨 마지막 원소는 제외하고 1번 과정을 한번 더 반복합니다. 최종적으로는 n-1번째에는 두 번째로 큰 원소가 오게됩니다. 이 과정을 n번 반복하면 정렬이 완료됩니다.

시간복잡도

시간복잡도는 이중 반복문으로 두 원소를 비교해 나가기 때문에, \(O(n^2)\) 입니다. 버블정렬은 미리 정렬이 되어있던 아니던 항상 비교하므로, 최악이던 최선이던 항상 \(O(n^2)\) 입니다.

공간복잡도

리스트 안에서 원소를 swap해가며 정렬하기 때문에, \(O(1)\) 입니다.

선택정렬 (Selection Sort)

선택정렬은 특정 위치에 들어갈 원소를 선택해서 정렬하는 알고리즘 입니다.

정렬 과정 (오름차순)

        
      
for i in range(n):
    idx = i
    for j in range(i + 1, n):
        if data[idx] > data[j]:
            idx = j
    data[idx], data[i] =\
     data[i], data[idx]

첫 번째 idx에 들어갈 수는 가장 작은 수 입니다. 1~n번째 원소를 순회하며 가장 작은 원소를 찾습니다.
가장 작은 원소를 찾으면 1번째 원소와 가장 작은 원소의 자리를 바꿉니다.
첫 번째 원소는 정렬되었으므로 제외하고 2~n 원소를 대상으로 다시 반복합니다. 이 과정을 모든 원소가 정렬 될 때 까지 n 반복하면 정렬이 완료됩니다.

시간복잡도

버블정렬과 마찬가지로 정렬이 어떻든 이중 반복문으로 탐색을 진행하기 때문에 최선, 평균, 최악 모두 \(O(n^2)\) 입니다.
다만 실제 실행 시간에서 차이나는 부분은 Swap 횟수 차이 때문입니다.

공간복잡도

버블정렬과 마찬가지로 주어진 리스트 안에서 Swap하기 때문에 \(O(1)\) 입니다.

삽입정렬 (Insertion Sort)

삽입정렬은 이름 그대로 원소가 들어갈 위치를 찾고, 해당 위치에 원소를 끼워 넣는 방식으로 정렬되는 알고리즘 입니다.

정렬 과정 (오름차순)

        
      
for i in range(1, n):
    number = data[i]
    idx = i - 1
    while idx >= 0 and data[idx] > number:
        data[idx + 1] = data[idx]
        idx -= 1
    data[idx + 1] = number

2번째 원소를 임시 저장하고, 첫 번재 원소와 비교해서 첫 번째 원소가 더 크면 오른쪽으로 첫 번째 원소를 한 칸 옮기고, 두 번째 원소를 첫 번째 자리로 옮깁니다.
3~n번째 원소에도 같은 과정을 반복합니다. n번 원소를 임시 저장하고, n-1~1까지 차례대로 비교하며 임시 저장한 원소보다 크면 오른쪽으로 옮깁니다. 만약 k번째 원소가 임시저장한 n번 원소보다 작다면, k+1위치에 임시저장한 원소를 넣고 사이클을 마무리합니다.
위 과정을 반복하다보면 정렬이 완료됩니다.

시간복잡도

삽입정렬은 기본적으로는 버블과 선택과 똑같이 \(O(n^2)\) 입니다. 정렬이 되어있지 않다면 이중 반복문을 실행하는것과 다르지 않기 때문입니다.

그러나, 이미 정렬이 되어있는 원소라면 while문은 조건에 맞지 않아 실행되지 않습니다. 그래서 최선의 상태라면 \(O(n)\) 입니다.

정리하자면 최선은 \(O(n)\), 평균과 최악은 \(O(n^2)\) 입니다.

공간복잡도

버블, 선택과 똑같이 주어진 리스트 내에서 Swap하며 정렬하므로 \(O(1)\) 입니다.

퀵정렬 (Qiuck Sort)

퀵정렬은 분할정복을 이용하는 정렬 알고리즘 입니다. 정렬의 기준이 되는 피벗(pivot)은 정하고, 피벗을 기준으로 큰 수와 작은 수를 나누는 과정을 반복하며 정렬합니다.

정렬 과정 (오름차순)

        
      
def partition(pdata, left, right):
    pivot = pdata[left]
    low = left
    high = right
    while low < high:
        while low < high and pdata[high] > pivot:
            high -= 1
        while low < high and pdata[low] <= pivot:
            low += 1
        pdata[low], pdata[high] = pdata[high], pdata[low]
    pdata[left], pdata[low] = pdata[low], pdata[left]
    return low

def sort(pdata, left, right):
    if left >= right: return
    pivot_idx = partition(pdata, left, right)
    sort(pdata, left, pivot_idx - 1)
    sort(pdata, pivot_idx + 1, right)

partition 함수
pivot을 기준으로 왼쪽에는 pivot보다 작은 수, 오른쪽에는 pivot과 같거나 큰 수를 배치한 후, pivot의 위치를 리턴하는 함수입니다.

범위 내에서 가장 왼쪽을 pivot으로 정합니다.
pivot보다 큰 수를 오른쪽으로 옮기기 위해 low 중 pivot보다 큰 수를 찾습니다.
pivot보다 작을 수를 왼쪽으로 옮기기 위해 high 중 pivot보다 작은 수를 찾습니다.
찾은 low와 high 위치의 두 원소를 swap하여 조건에 맞는 리스트를 만듭니다. 이 과정을 low와 high가 만날때까지 반복합니다.
pivot보다 작은 수는 left~low, pivot보다 같거나 큰 수는 high~right 범위에 배치되었으므로 pivot 위치와 low 위치의 원소를 바꿔 중간에 pivot이 위치하게 합니다. 최종적으로 pivot은 정렬된 위치에 있게 됩니다.

partion을 실행하고 나면 pivot을 기준으로 좌측에는 pivot보다 작은 수가 정렬되지 않은 상태로, 우측에는 pivot보다 큰 수가 정렬되지 않은 상태로 있게됩니다.

sort 함수
정렬 리스트를 분할하는 함수입니다.

0~n 범위에서 partion을 진행합니다.
partion 실행으로 얻은 pivot을 기준으로 좌 우 두 리스트로 나눕니다. 이 과정을 분할된 리스트의 크기가 0~1이 될때까지 반복합니다.

시간복잡도

최선의 경우에는 분할하는 과정이 \(\log_2{n}\) 번, 각 단계마다 정렬하는 과정이 \(n\) 번 진행되므로 \(O(n\log{n})\) 입니다.

그러나 이미 정렬이 되어있는 상황과 같이 pivot을 기준으로 절반으로 나눠지지 않는 경우에는 다릅니다. 분할하는 과정이 \(n\)번, 각 단계마다 정렬하는 과정이 \(n\)번 진행되므로 최악의 경우에는 \(O(n^2)\) 입니다.

정리하자면 최악은 \(O(n^2)\), 평균/최선은 \(O(n\log{n})\) 입니다.

공간복잡도

버블, 선택, 퀵과 똑같이 주어진 리스트 내에서 Swap하며 정렬하므로 \(O(1)\) 입니다. 그런데 한가지 함정이 있는데, 위와같이 재귀함수 형태로 구현하게 되면 재귀함수 stack 메모리가 추가로 필요하므로 최소 \(O(\log{n})\), 최대 \(O(n)\)가 됩니다.

병합정렬 (Merge Sort)

병합정렬은 퀵정렬과 마찬가지로 분할정복을 이용해서 정렬하는 알고리즘 입니다. 차이점이라면 퀵정렬은 pivot을 기존으로 쪼갰다면, 병합정렬은 무조건 index의 중앙을 기준으로 쪼개서 정렬합니다.

정렬 과정 (오름차순)

        
      
def merge(pdata, left, right, mid):
    data_left = pdata[left:mid + 1]
    data_right = pdata[mid + 1:right + 1]
    i = j = 0
    k = left

    while i < len(data_left) and j < len(data_right):
        if data_left[i] < data_right[j]:
            pdata[k] = data_left[i]
            i += 1
        else:
            pdata[k] = data_right[j]
            j += 1
        k += 1

    while i < len(data_left):
        pdata[k] = data_left[i]
        i += 1
        k += 1

    while j < len(data_right):
        pdata[k] = data_right[j]
        j += 1
        k += 1

def sort(pdata, left, right):
    if left >= right: return
    mid = (left + right) // 2
    sort(pdata, left, mid)
    sort(pdata, mid + 1, right)
    merge(pdata, left, right, mid)

sort 함수
리스트를 정확히 두 개로 분할하는 함수입니다.

0~n 범위에서 mid를 구한 후 0~mid, mid+1~n 범위로 나눕니다.
그 과정을 분할된 리스트의 크기가 0~1이 될때까지 재귀적으로 반복합니다.
분할된 두 범위를 대상으로 merge합니다.

merge 함수
분할된 두 리스트를 이용해 정렬하는 함수입니다.

left~mid, mid+1~right 범위를 각각 별도의 리스트로 분리합니다.
두 리스트를 각각 왼쪽부터 하나씩 비교해가며 더 작은 수를 정렬 리스트에 넣습니다. 이 과정을 둘 중 한 리스트를 다 넣을때까지 반복합니다.
두 리스트 중 남은 리스트를 전부 정렬 리스트에 넣습니다.

시간복잡도

병합정렬은 정렬 할 리스트의 상태가 어떻든 일단 무조건 반으로 나눠서 분할정복으로 정렬하기 때문에 최악, 평균, 최선 모두 \(O(n\log{n})\) 입니다.

공간복잡도

병합정렬은 merge 과정에서 추가적인 리스트가 필요합니다. 그래서 공간복잡도는 \(O(n)\) 입니다.

힙정렬 (Heap Sort)

힙정렬은 힙 자료구조를 기반으로 정렬하는 알고리즘 입니다. 그래서 힙정렬을 이해하려면 일단 힙 자료구조를 알아야 합니다.
힙을 모르신다면 [자료구조] C로 Heap 만들기를 먼저 읽고 마저 읽으시는걸 추천합니다.

힙정렬 힙 활용방법

힙정렬에서는 내림차순 정렬에는 최대힙(Max Heap)을, 오름차순 정렬에서는 최소힙(Min Heap)을 활용합니다. 정렬이 필요한 리스트를 힙으로 구성 후, 루트 노드를 하나씩 제거하며 가져오는 방식으로 정렬합니다.

정렬 과정 (오름차순)

        
      
min_heap = []

def insert(heap: list, value):
    heap.append(value)
    index = len(heap) - 1
    while index > 0 and heap[index] < heap[(index - 1) // 2]:
        heap[index], heap[(index - 1) // 2] = heap[(index - 1) // 2], heap[index]
        index = (index - 1) // 2

def delete(heap: list):
    if len(heap) == 0: return -1

    if len(heap) == 1:
        return heap.pop()
    
    root_value = heap[0]

    heap[0] = heap.pop()
    index = 0
    while 1:
        smallest = index
        left_child = index * 2 + 1
        right_child = index * 2 + 2

        if left_child < len(heap) and heap[left_child] < heap[smallest]:
            smallest = left_child
        if right_child < len(heap) and heap[right_child] < heap[smallest]:
            smallest = right_child
        if smallest == index: break

        heap[index], heap[smallest] = heap[smallest], heap[index]
        index = smallest

    return root_value

....

for i in data:
    insert(min_heap, i)

for j in range(len(data)):
    data[j] = delete(min_heap)

사실 코드를 보면 알겠지만, 힙에 그냥 전부 넣고 전부 빼는거 말고는 특별할게 없습니다.

시간복잡도

힙정렬은 원래 리스트의 상태가 어떻든 힙 insert후 delete를 수행하기 때문에, 최악, 평균, 최선 모두 \(O(n\log{n})\) 입니다. \(n\) 개의 원소를 \(\log{n}\) level을 거쳐 업데이트 하기 떄문입니다.

공간복잡도

힙정렬에서 현재 제가 구현한 방식은 \(O(n)\) 입니다. 힙의 메모리도 n 크기만큼 추가적으로 필요하기 때문입니다.

다만 heapify 알고리즘을 사용하면 추가적인 힙 리스트 생성 없이 기존 리스트를 힙의 성질을 만족하게 바꿀 수 있기 때문에 \(O(1)\) 도 가능합니다.

[Algorithm] 정렬 알고리즘 알아보기

거픔정렬 (Bubble Sort)

정렬 과정 (오름차순)

시간복잡도

공간복잡도

선택정렬 (Selection Sort)

정렬 과정 (오름차순)

시간복잡도

공간복잡도

삽입정렬 (Insertion Sort)

정렬 과정 (오름차순)

시간복잡도

공간복잡도

퀵정렬 (Qiuck Sort)

정렬 과정 (오름차순)

시간복잡도

공간복잡도

병합정렬 (Merge Sort)

정렬 과정 (오름차순)

시간복잡도

공간복잡도

힙정렬 (Heap Sort)

힙정렬 힙 활용방법

정렬 과정 (오름차순)

시간복잡도

공간복잡도

관련된 글

[OS] 프로세스 메모리 구조

[자료구조] C로 Heap 만들기

[Network] HTTP와 HTTPS: Handsake 과정