[쓰면서 익히는 알고리즘과 자료구조](8) 정렬(Sort)

8.1 거품 정렬(Bubble Sort)

거품 정렬은 정렬 중에서 가장 직관적인 정렬 방식이다.

 

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

---

8.2 삽입 정렬(Insertion Sort)

def insertion_sort(arr):
    n = len(arr)

    for i in range(1, n):
        key_item = arr[i]

        j = i - 1

        while j >= 0 and arr[j] >= key_item:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key_item

    return arr

코드가 살짝 꼬여(?) 있는데 이게 왜 삽입 정렬이냐면,

현재 item = key_item보다 배열에 이전 요소들이 크면 오른쪽으로 한 칸씩 민다. ( 현재 key_item)이 들어갈 공간 확보, 그리고 key_item보다 작은 요소를 찾으면 그 작은 요소의 다음 위치에 key_item 을 밀어 넣는다. ( key_item 보다 큰 요소는 한 칸 씩 다 밀려있음)

현재 배열의 상태가 [1 3 5 7 4 ] 이고, 7까지 오름차순으로 정렬이 되어 있다.

 

4를 삽입 정렬로 넣고 싶으면 다음과 같은 과정을 거치는 것이다.

 

[1 3 5 7 4 ], key_item = 4

[1 3 5 7 7 ], key_item = 4

[1 3 5 5 7 ], key_item = 4

[1 3 4 5 7 ], key_item = 4

 

삽입정렬은 적은 데이터 개수를 가지는 데이터 셋에서 다른 정렬보다 평균적으로 좋은 성능을 가진다. 최신 C++ 에서 사용되는 내장 정렬 함수는 작은 데이터 셋에 대해 삽입 정렬을 사용하도록 구현되어 있다.

 

---

8.3 병합 정렬(Merge Sort)

거품 정렬과 삽입 정렬보다 높은 효율을 보이는 정렬 알고리즘이다.

병합 정렬은 분할 정복 접근을 기반으로 복잡한 문제를 해결 할 때 사용하는 강력한 알고리즘 기술이다.

병합 정렬은 안정적으로 시간 복잡도 O(n logn)을 지원한다.

 

def merge(left, right):
    left_len = len(left)
    right_len = len(right)

    result = []
    left_index = right_index = 0

    while len(result) < left_len + right_len:
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1

        if right_index == right_len:
            result.extend(left[left_index:])
            break

        if left_index == left_len:
            result.extend(right[right_index:])
            break

    return result


def merge_sort(arr):
    n = len(arr)
    if n < 2:
        return arr

    mid_index = n // 2
    left = merge_sort(arr[:mid_index])
    right = merge_sort(arr[mid_index:])
    return merge(left, right)

---

8.4 퀵 정렬(Quick Sort)

병합 정렬과 비슷하게 분할 정복 방법을 이요한 방식이다.

다른 점은 입력 리스트를 두 리스트로 나눌 때 한 쪽은 특정 값보다 작은 값만 모으고 다른 하나는 특정 값보다 큰 값만 모은다.

특정 값을 피벗(Pivot)이라고 부르는데 피벗을 결정하는 방식에 따라 성능 차이가 발생하기도 한다.

 

from random import randint


def quicksort(arr):
    arr_len = len(arr)
    if arr_len < 2:
        return arr

    low, same, high = [], [], []

    pivot = arr[randint(0, arr_len - 1)]
    
    for item in arr:
        if item < pivot:
            low.append(item)
        elif item == pivot:
            same.append(item)
        elif item > pivot:
            high.append(item)
    
    return quicksort(low) + same + quicksort(high)

 

극단적으로 임의 값이 매번 가장 작은 값이거나 가장 큰 값이라면, n 번 분리되고 n 번 합치는 과정이 필요해 최악의 상황인 O(n^2) 이 되지만 평균적으로는 O(n logn)이 되는 정렬 알고리즘이다.

피벗을 선택할 때 무조건 중앙값으로 선택할 수만 있다면 안정적으로 O(n logn)의 성능을 유지할 수 있다.

---

8.5 팀 정렬(Tim Sort)

팀 정렬은 2002년 팀 피터(Tim Peter)에 의해 파이썬에 구현되여 2.3부터 적용된 내장 정렬이다.

작은 크기의 리스트의 경우 잘게 쪼개 삽입 정렬로 정렬하고, 병합 정렬의 병합 부분을 채용해 정렬된 리스트를 합치도록 한다.

C++에서도 팀 정렬과 비슷하게 최적화된 정렬 조합으로 안정적이고 빠르게 정렬을 지원하는 인트로 정렬(Intro Sort)이 있다.

 

def binary_search(arr, key, start, end):
    if end - start <= 1:
        if arr[start] > key:
            return start - 1
        else:
            return start

    mid = (start + end) // 2

    if arr[mid] < key:
        return binary_search(arr, key, mid, end)
    elif arr[mid] > key:
        return binary_search(arr, key, start, mid)
    else:
        return mid


def insertion_sort(arr, run_s=0, run_e=None):
    if run_e is None:
        run_e = len(arr) - 1

    for i in range(run_s + 1, run_e + 1):
        v = arr[i]
        pos = binary_search(arr, v, run_s, i) + 1

        for k in range(i, pos, -1):
            arr[k] = arr[k - 1]
        arr[pos] = v


def merge(left, right):
    left_len = len(left)
    right_len = len(right)

    result = []
    left_index = right_index = 0

    while len(result) < left_len + right_len:
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1

        if right_index == right_len:
            result.extend(left[left_index:])
            break

        if left_index == left_len:
            result.extend(right[right_index:])
            break

    return result


def timsort(arr):
    min_run = 32
    n = len(arr)

    for i in range(0, n, min_run):
        insertion_sort(arr, i, min((i + min_run - 1), n - 1))

    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            mid = start + size - 1
            end = min((start + size * 2 - 1), (n - 1))

            merged = merge(arr[start:mid + 1], arr[mid + 1:end + 1])
            arr[start:start + len(merged)] = merged
        size *= 2
    return arr


from random import randint

input_arr = [randint(0, 100) for i in range(100)]
res = timsort(input_arr)
print(f'sorted {res}')
print(f'{sorted(input_arr) == res}')

---

마무리

좋은 개발자를 채용하는 과정은 컴퓨터 과학 지식과 더불어 알고리즘 및 자료구조에 대한 이해도를 많이 평가한 다는 것이었고, 그것들이 개발 역량을 높이는데 필수적인 것임을 알게되었다.

 

이 책은 필자가 기초적인 패턴 중심으로 공부하며 기록한 내용을 정리한 것이다. 다양한 접근을 통해 어떤 식으로 문제를 해결할 수 있을지에 대한 가이드가 되길 기대한다.

 

여기서 가장 중요한 것은 ‘어떻게 노트에 정리하고 기억할 수 있도록 하는가’이다. 자신만의 언어로 이해할 수 있는 정리 법을 파악하고 기록하자.

 

알고리즘과 자료구조의 학습은 장기전이기 때문에 오랜 시간 꾸준히 공부할 수 있도록 컨디션 조절과 실천 가능한 계획을 세우는 것이 중요하다.

 

끝까지 포기하지 말고 알고리즘과 자료구조 학습으로 스스로 발전된 모습을 느껴보길 바란다.