[CS공부] 6. 정렬 알고리즘(2)

깃허브 정리본

용어

• shell sorting(셸 정렬): 단순 삽입 정렬의 방법을 유지하되, h값으로 배열의 원소들을 grouping해 각 그룹별로 단순 삽입 정렬하는 것을 반복하는 알고리즘
  -> 불안정적인 정렬 알고리즘, 퀵정렬 고안 전까지 가장 빨랐던 알고리즘, 시간 복잡도 O(n^1.25)

• quick sorting(퀵 정렬): pivot을 기준으로 배열을 grouping하여, 모든 group이 1개의 원소가 될때까지 반복하는 알고리즘
  -> 불안정적인 정렬 알고리즘, 가장 빠른 정렬 알고리즘으로 알려져 있음, 시간 복잡도 O(nlogn)

실습

셸 정렬

"""
기본 개념: 정렬할 배열의 원소를 그룹으로 나누고 각 그룹별로 정렬.
=> h값의 수열은 그룹들이 서로 겹치지 않게 하는게 좋음. 즉 h값들이 서로 배수관계가 되지 않도록 함.
=> ex) 수열을 3i+1로 하고, 초기 h값을 n//9를 넘지 않도록 함.
"""
def shell_sorted(lst: list) -> list:
    n = len(lst)
    h = 1
    while h < n // 9:
        h = h * 3 + 1

    while h > 0:
        for i in range(h, n):
            j = i - h
            temp = lst[i]
            while j >= 0 and lst[j] > temp:
                lst[j + h] = lst[j]
                j -= h
            lst[j+h] = temp
        h //= 3
    return lst

lst_1 = [1, 3, 9, 4, 11, 7, 88, 8, 6]

print(shell_sorted(lst_1))


# 실행결과 ==========================================
[1, 3, 4, 6, 7, 8, 9, 11, 88]

퀵 정렬 - 재귀적 구현

"""
기본 개념: pivot값을 기준으로 pointer left, right로 나눠 스캔하며 그루핑
=> pivot을 어떻게 설정하느냐가 정렬의 성능에 영향을 미침.
=> 배열의 중앙값을 pivot으로 삼아 재귀적으로 구현한 방식
"""
def qsort(lst: list, left: int, right: int) -> None:
    pointer_left = left
    pointer_right = right
    pivot = lst[(left + right) // 2]

    print(f"list[{left}] ~ list[{right}]:", *lst[left: right + 1])

    while pointer_left <= pointer_right:
        while lst[pointer_left] < pivot: pointer_left += 1
        while lst[pointer_right] > pivot: pointer_right -= 1
        if pointer_left <= pointer_right:
            lst[pointer_left], lst[pointer_right] = lst[pointer_right], lst[pointer_left] 
            pointer_left += 1
            pointer_right -= 1
    
    if left < pointer_right: qsort(lst, left, pointer_right)
    if right > pointer_left: qsort(lst, pointer_left, right)


def quick_sorted(lst: list) -> list:
    qsort(lst, 0, len(lst) - 1)
    return lst


lst_1 = [1, 3, 9, 94, 82, 4, 11, 77, 7, 88, 8, 104, 6]

print(quick_sorted(lst_1))


# 실행결과 ==========================================
list[0] ~ list[12]: 1 3 9 94 82 4 11 77 7 88 8 104 6
list[0] ~ list[6]: 1 3 9 6 8 4 7
list[0] ~ list[2]: 1 3 4
list[4] ~ list[6]: 8 9 7
list[4] ~ list[5]: 8 7
list[7] ~ list[12]: 77 11 88 82 104 94
list[7] ~ list[9]: 77 11 82
list[8] ~ list[9]: 77 82
list[10] ~ list[12]: 88 104 94
list[10] ~ list[11]: 88 94
[1, 3, 4, 6, 7, 8, 9, 11, 77, 82, 88, 94, 104]

퀵 정렬 - 비재귀적 구현

"""
=> 퀵 정렬의 비재귀적 구현 방식으로, 간단한 Stack을 통해 구현
"""
from typing import Any


class FixedStack:

    class Empty(Exception): pass

    class Full(Exception): pass

    def __init__(self, capacity: int = 256) -> None:
        self.stack = [None] * capacity
        self.capacity = capacity
        self.pointer = 0
    
    def is_empty(self) -> bool:
        return self.pointer <= 0
    
    def push(self, value: Any) -> None:
        if self.pointer >= self.capacity: raise FixedStack.Full
        self.stack[self.pointer] = value
        self.pointer += 1
        return self.pointer >= self.capacity
    
    def pop(self) -> Any:
        if self.is_empty(): raise FixedStack.Empty
        self.pointer -= 1
        return self.stack[self.pointer]


def quick_sorted(lst: list) -> list:
    n = len(lst)
    stack = FixedStack(n)
    stack.push((0, n-1))

    while not stack.is_empty():
        pointer_left, pointer_right = left, right = stack.pop()
        pivot = lst[(left + right)//2]

        print(f"list[{left}] ~ list[{right}]:", *lst[left: right + 1])

        while pointer_left <= pointer_right:
            while lst[pointer_left] < pivot: pointer_left += 1
            while lst[pointer_right] > pivot: pointer_right -= 1
            if pointer_left <= pointer_right:
                lst[pointer_left], lst[pointer_right] = lst[pointer_right], lst[pointer_left] 
                pointer_left += 1
                pointer_right -= 1
    
        if left < pointer_right: stack.push((left, pointer_right))
        if right > pointer_left: stack.push((pointer_left, right))
    return lst


lst_1 = [1, 3, 9, 94, 82, 4, 11, 77, 7, 88, 8, 104, 6]

print(quick_sorted(lst_1))


# 실행결과 ==========================================
list[0] ~ list[12]: 1 3 9 94 82 4 11 77 7 88 8 104 6
list[7] ~ list[12]: 77 11 88 82 104 94
list[10] ~ list[12]: 88 104 94
list[10] ~ list[11]: 88 94
list[7] ~ list[9]: 77 11 82
list[8] ~ list[9]: 77 82
list[0] ~ list[6]: 1 3 9 6 8 4 7
list[4] ~ list[6]: 8 9 7
list[4] ~ list[5]: 8 7
list[0] ~ list[2]: 1 3 4
[1, 3, 4, 6, 7, 8, 9, 11, 77, 82, 88, 94, 104]

정리

위에서는 퀵 정렬의 pivot값을 단순히 중앙값으로 정했다.

하지만 이조차도 '시작/중앙/끝값 중 중간값으로 pivot을 정한다' 등
방법을 조금만 바꿔줘도 정렬효율이 올라간다고 한다.

또한, 현재는 stack의 크기를 배열의 길이(n)와 같게 지정했는데,
'원소수가 적은 그룹을 먼저 처리'하는 등의 아이디어만 넣어줘도
필요한 stack의 크기가 획기적으로 줄어든다고 한다.
(공간 복잡도가 감소한다)

정말 작은 부분 하나까지 말그대로 '최적화'가 가능하구나 싶었다.
이런 개발을 지향해야지..