[SW 정글 8일차] 정렬 알고리즘 2

오늘은 어제에 이어 정렬 알고리즘에 대해 더 공부해보려고 한다.

정렬 알고리즘만 이틀연속 공부한 것이 아니라 토요일부터 재귀함수의 늪에 빠져 헤어나오느라 시간을 꽤 많이 소비했다.

어제는 기본 정렬 알고리즘을 공부했다면 오늘은 시간복잡도 면에서 더 개선된 알고리즘을 공부하여 정리해보려고 한다.

 

 

1. 셸 정렬 (shell sort)

셸 정렬은 단순 삽입 정렬의 문제점을 보완하여 더 좋은 시간복잡도를 가지는 알고리즘이다.

단순 삽입 정렬의 문제점은 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아지는 것이다.

아래의 배열을 보면 다섯 번째 위치에 있는 0은 앞의 것이 정렬되어있음에도 불구하고 삽입 정렬을 위해 5번에 걸쳐 이동해야한다.

이를 보완하기 위해 셸 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나눠 각 그룹별로 정렬을 수행한다.

그리고나서 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄이는 방법이다.

먼저, 셸 정렬의 코드를 봐보자.

def shell_sort(arr):
    length_arr = len(arr)
    h = length_arr // 2
    while h > 0:
        for i in range(h, n):
            j = i - h
            tmp = a[i]
            while j >= 0 and a[j] > tmp:
                a[j + h] = a[j]
                j -= h
            a[j + h] = tmp
        h //= 2

코드를 보면 단순 삽입 정렬과 비슷하지만 다른 점은 h라는 변수를 사용해 이웃한 원소끼리 비교하는 것이 아닌 h만큼 떨어져있는 원소와 비교한다는 것이다.

h의 초기값은 배열의 길이의 절반이고 정렬을 할때마다 절반씩 줄어든다.

셸 정렬 알고리즘의 시간복잡도는 O(n^1.25)이고 이웃하지 않고 떨어져 있는 원소를 서로 교환하므로 안정적이지 않은 알고리즘이다.

 

 

2. 퀵 정렬 (quick sort)

퀵 정렬은 정렬 알고리즘 중 가장 빠른 정렬 알고리즘으로 보편적으로 많이 사용하는 알고리즘이다.

퀵 정렬은 어떠한 기준 원소를 잡고 그 원소보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 보내는 것이다.

여기서 기준 원소를 피벗(pivot)이라고 부른다.

그림을 보며 이해해보자.

아래의 배열에서 가운데 위치한 원소인 3을 기준으로 잡는다.

그리고 맨 왼쪽을 가리키는 포인터와 맨 오른쪽을 가리키는 포인터를 설정한다.

피벗보다 작은 값이 있는 그룹과 큰 값이 있는 그룹으로 나누려면 피벗 이하인 원소를 배열 왼쪽으로 피벗 이상인 원소를 배열 오른쪽으로 이동시켜야 한다.

즉, 왼쪽에 있는 포인터는 피벗값보다 크거나 같은 값을 찾을 때까지 포인터를 오른쪽 방향으로 이동시키면서 스캔한다.

오른쪽에 있는 포인터는 피벗값보다 작거나 같은 값을 찾을 때까지 포인터를 왼쪽 방향으로 이동시키면서 스캔한다.

그러면 아래와 같이 포인터가 멈출 것이다.

여기서 왼쪽 포인터와 오른쪽 포인터가 가리키는 원소끼리 swap을 한다.

그 후에 계속해서 스캔을 하면 아래와 같은 상황에서 멈추게 될 것이다.

마찬가지로 서로 swap을 해주고 나면 이후에는 왼쪽에서 시작한 포인터와 오른쪽에서 시작한 포인터가 서로 교차할 것이다.

그러면 두 개의 그룹으로 나누는 과정이 끝나고 계속해서 그룹을 나누다보면 피벗과 일치하는 그룹이 만들어질 수 있다.

위 경우에서는 피벗과 일치하는 그룹이 만들어지지 않았지만 왼쪽 포인터와 오른쪽 포인터가 동시에 피벗을 가리키는 경우가 생길 것이다.

피벗과 일치하는 그룹이 만들어지는 경우는 왼쪽 포인터 인덱스 > (오른쪽 포인터 인덱스 + 1)일 경우이다.

아래의 코드는 피벗을 배열의 가운데 원소로 잡고 두 개의 그룹으로 나누는 것이다.

def partition(arr):
    length_arr = len(arr)
    left_pointer = 0
    right_pointer = length_arr - 1
    pivot = arr[n // 2]
    
    while left_pointer <= right_pointer:
        while arr[left_pointer] < pivot:
            left_pointer += 1
        
        while arr[right_pointer] > pivot:
            right_pointer -= 1
        
        if left_pointer <= right_pointer:
            arr[left_pointer], arr[right_pointer] = arr[right_pointer], arr[left_pointer]
            left_pointer += 1
            right_pointer -= 1

위 코드를 이용해서 한 개 원소만 가진 그룹이 될 때까지 반복하면 된다.

여기서, 원소 수가 1개인 그룹은 더 이상 쪼개질 수 없으므로 그룹 나누기를 반복하는 제한하는 조건을 걸어주어야한다.

1) 오른쪽 포인터가 배열의 첫 뻔째 위치보다 오른쪽에 위치하면 왼쪽 그룹을 나눈다.

2) 왼쪽 포인터가 배열을 마지막 위치보다 왼쪽에 위치하면 오른쪽 그룹을 나눈다.

 

그러면 퀵 정렬 알고리즘 코드를 봐보자.

def qsort(arr, left, right):
    left_pointer = left
    right_pointer = right
    x = arr[(left + right) // 2]

    while left_pointer <= right_pointer:
        while arr[left_pointer] < x:
            left_pointer += 1
        while arr[right_pointer] > x:
            right_pointer -= 1

        if left_pointer <= right_pointer:
            arr[left_pointer], arr[right_pointer] = arr[right_pointer], arr[left_pointer]
            left_pointer += 1
            right_pointer -= 1

    if left < right_pointer:
        qsort(arr, left, right_pointer)
    if left_pointer < right:
        qsort(arr, left_pointer, right)

아래 4줄의 코드를 보면 2개 이상의 원소를 가진 그룹에 한해서 다시 재귀로 그룹을 나누는 과정을 반복하는 것을 볼 수 있다.

 

이러한 퀵 정렬은 시간 복잡도가 O(nlogn)으로 어제 배운 기본 정렬 알고리즘보다 좋은 시간 복잡도를 가지고 있다.

하지만, 두 개의 그룹으로 나눌 때 매번 한 개의 원소와 나머지 원소로 나뉜다면 시간 복잡도는 O(n^2)이 될 것이다.

그리고 퀵 정렬은 서로 이웃하지 않는 원소를 교환하므로 안정적이지 않은 알고리즘이다.

 

 

 

3. 병합 정렬 (merge sort)

병합 정렬은 배열을 미리 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하여 정렬을 하는 알고리즘이다.

두 그룹으로 나누어 정렬하는 것은 잠시 후에 알아보고 병렬하는 과정을 먼저 알아보자.

각 배열에 포인터를 두어 포인터가 가리키는 원소의 값을 비교하여 작은 쪽의 원소를 꺼내 새로운 배열에 저장한다.

이 작업을 반복하여 정렬을 마친 배열을 만든다.

그러면 병합 정렬을 구현한 코드를 봐보자.

def merge_sort(arr):

    def _merge_sort(arr, left, right):
        if left < right:
            center = (left + right) // 2

            _merge_sort(arr, left, center)
            _merge_sort(arr, center + 1, right)

            p = j = 0
            i = k = left

            while i <= center:
                buff[p] = arr[i]
                p += 1
                i += 1

            while i <= right and j < p:
                if buff[j] <= arr[i]:
                    arr[k] = buff[j]
                    j += 1

                else:
                    arr[k] = arr[i]
                    i += 1
                k += 1


            while j < p:
                arr[k] = buff[j]
                k += 1
                j += 1

    n = len(arr)
    buff = [None] * n
    _merge_sort(arr, 0, n - 1)

코드를 보면 병합 정렬을 하기 전에 병합 후에 원소를 담을 buff라는 배열을 선언해준다.

그 후, 실질적으로 병합 정렬을 하는 함수를 실행하는데 코드를 보면 앞 부분과 뒷 부분을 나눠 재귀로 정렬을 실행하는 것을 알 수 있다.

병합 정렬의 총 시간 복잡도는 O(nlongn)이고 서로 떨어져 있는 원소를 교환하지 않아 안정적인 알고리즘이다.

 

 

 

3. 힙 정렬 (heap sort)

힙 정렬은 heap이라는 자료구조의 특성을 이용하여 정렬하는 알고리즘이다.

heap의 특성은 '부모의 값이 자식의 값보다 항상 크다' 혹은 '부모의 값이 자식의 값보다 항상 작다'라는 조건을 만족하는 완전 이진 트리이다.

힙 정렬은 이러한 특성을 이용하여 정렬하는데 아래와 같은 작업을 반복한다.

1) 힙에서 최댓값인 루트를 꺼낸다.

2) 루트 이외의 부분을 힙으로 만든다.

 

여기서 루트를 꺼내고 남은 원소를 다시 힙으로 만드는 것은 기존의 힙에서 마지막 원소를 루트로 이동시키고 자신보다 큰 자식과 자리를 바꾸면서 아래쪽으로 내려가는 작업을 반복한다.

이러한 작업을 반복하면서 리프의 위치에 도달하거나 자식의 값이 더 이상 큰 것이 없으면 정지한다.

 

그러면 힙 정렬은 어떻게 구현될까?

(여기서 구현하는 것은 오름차순 기준이다.)

예를 들어, 배열의 길이가 7인 배열을 생각해보자.

먼저, 배열을 최대 힙으로 만들고 루트 원소와 배열의 마지막 원소와 교환한다.

그 다음에는 맨 끝을 제외한 [0] ~ [5]까지를 다시 맥스힙으로 만든다.

이 후에 루트 값과 [5] 원소와 교환하고 다시 남은 [0] ~ [4]를 맥스힙으로 만들면서 반복하는 것이다.

 

이제 힙 정렬을 구현한 코드를 봐보자.

def heap_sort(arr):

    def down_heap(arr, left, right):
        temp = arr[left]
        parent = left
        while parent < (right + 1) // 2:
            child_left = parent * 2 + 1
            child_right = child_left + 1
            child = child_right if child_right <= right and arr[child_right] > arr[child_left] else child_left
            if temp >= arr[child]:
                break
            arr[parent] = arr[child]
            parent = child
        arr[parent] = temp

    n = len(arr)

    for i in range((n - 1) // 2, -1, -1):
        down_heap(arr, i, n - 1)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        down_heap(arr, 0, i - 1)

down_heap() 함수는 배열을 힙으로 만들어주는 역할을 하고 heap_sort()로 힙 정렬이 이루어진다.

힙 정렬의 시간복잡도는 최댓값인 원소를 선택하는 시간 복잡도 O(n)과 힙으로 만드는 작업이 O(log n)으로 총 O(nlog n)의 시간복잡도를 가진다.

 

 

 

4. 도수 정렬 (counting sort)

도수 정렬은 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘으로 분포수 세기 정렬(distribution counting)이라고도 한다.

이전까지 알아본 정렬 알고리즘은 두 원소의 값을 비교하여 정렬했지만 도수 정렬은 원소를 비교할 필요가 없다는 것이 특징이다.

도수 정렬을 구현한 코드는 아래와 같다.

def fsort(arr, max_num):
    n = len(arr)
    f = [0] * (max_num + 1)
    b = [0] * n

    for i in range(n):
        f[arr[i]] += 1

    for i in range(1, max_num + 1):
        f[i] += f[i - 1]

    for i in range(n - 1, -1, -1):
        f[arr[i]] -= 1
        b[f[arr[i]]] = arr[i]
        
    for i in range(n):
        arr[i] = b[i]

def counting_sort(a):
    fsort(a, max(a))

 

 

 

---

오늘은 어제부터 문제풀이를 잠깐 멈추고 정렬 알고리즘 개념을 확실히 잡고자 시간을 투자했다.

나는 정글에 들어오기 전 내가 생각하기에는 코딩 테스트를 꽤 준비했다고 생각하는데 나보다 알고리즘 문제를 푸는 접근 속도가 빠른 사람이 꽤 많다.

문제 이해도나 문제를 봤을 때 어떻게 접근해야하는지 등에 대한 생각속도가 빠르고 그 생각을 코드로 구현하는 실력이 좋은 사람들이 많은 것같다.

이러한 사람들을 보면 부럽지만 너무 조급해하지말고 나만의 방식, 페이스로 달려갈 생각이다.

지금 주어진 시간은 문제 빨리푸는 방법을 익히는 것이 아닌 지금까지 알고 있었던 자료구조, 알고리즘 개념을 제대로 잡고 이 개념을 도입해서 문제에 어떻게 접근하는지를 연습하는 기간이라고 생각한다.

절대 조급해하지말고 내 앞에 있는 것을 내가 생각한대로 차근차근 해결해나가자.

 

---

<참고 자료>

자료구조와 함께 배우는 알고리즘 입문 파이썬 편 (저자 Bohyoh Shibata, 옮김 강민)