알고리즘 - 퀵 정렬(2)

퀵 정렬을 비재귀적으로도 만들 수 있습니다.

스택을 사용해 만들어보겠습니다.

 

먼저 사용할 스택 코드입니다.

from typing import Any

class FixedStack:
    #고정 길이 스택 클래스

    class Empty(Exception):
        #비어 있는 FixedStack에 팝 또는 피크할 때 내보내는 예외 처리
        pass

    class Full(Exception):
        # 가득 찬 FixedStack에 푸시할 때 내보내는 예외 처리
        pass

    def __init__(self, capacity: int = 256) -> None:
        # 스택 초기화
        self.stk = [None] * capacity    # 스택 배열
        self.capacity = capacity    # 스택의 크기
        self.ptr = 0    # 스택 포인터    

    def is_empty(self) -> bool:
        # 스택이 비어있는지 판단
        return self.ptr <= 0

    def is_full(self) -> bool:
        # 스택이 가득 차 있는지 판단
        return self.ptr >= self.capacity

    def push(self, value: Any) -> None:
        # 스택에 데이터를 푸시
        if self.is_full():
            raise FixedStack.Full   # 스택이 가득차 있는지 확인
        self.stk[self.ptr] = value  # 현재 포인터에 데이터를 넣어주고
        self.ptr += 1   # 포인터에 + 1

    def pop(self) -> Any:
        # 스택에서 데이터를 팝(꺼내옴)
        if self.is_empty():
            raise FixedStack.Empty  # 스택이 비어 있는지 확인
        self.ptr -= 1   # 데이터의 개수를 뜻하므로 -1한 값이 최종 인덱스 값과 같습니다.
        return self.stk[self.ptr]   # 가장 위에 데이터를 리턴
    

 

퀵 정렬 코드입니다.

from chap4.fixed_stack import FixedStack

def qsort(a, left: int, right: int) -> None:
    range = FixedStack(right - left + 1)

    range.push((left, right))

    while not range.is_empty():
        pl, pr = left, right = range.pop()
        x = a[(left + right) // 2]  # 가운데 원소

        while pl <= pr:
            while a[pl] < x: pl += 1
            while a[pr] > x: pr -= 1
            if pl <= pr:
                a[pl], a[pr] = a[pr], a[pl]
                pl += 1
                pr -= 1

        if left < pr: range.push((left, pr))
        if pl < right: range.push((pl, right))


print('퀵 정렬(비재귀)')
num = int(input('원소 수 입력: '))
x = [None] * num

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

qsort(x, 0, len(x)-1)

print('오름차순 퀵 정렬')
print(''.join(str(x)))

 

qsort 함수를 보겠습니다.

먼저 원소의 수만큼 스택의 크기를 정해줍니다.

 

여기서 사용하는 left, right는 범위라고 생각하시면 됩니다.

스택에 push를 이용해 범위를 튜플형으로 넣어줍니다.

 

첫 번째 while문은 스택이 비어있으면 멈추게 하고

pl, pr을 각각 스택에서 pop한 값들로 넣어줍니다.

 

두 번째 while문은 이전과 같기 때문에 넘어가겠습니다.

 

마지막 if문을 보면 다시 스택에 범위를 넣어줍니다.

처음들어온 범위가 (0, 8)이라면 if문을 통해 (0, 4), (5, 8)이 들어가고

스택 top에는 (5, 8)이 있고 이것을 다시 (5, 6), (7, 8)로 

(7, 8)을 분할, (5, 6)을 분할 해서, 각 그룹에 하나씩으로 분할을 끝냈습니다.

이제 마지막으로 남은 (0, 4)를 (5, 8)과 마찬가지로 분할을 하면 정렬이 끝나게됩니다.

 

퀵 정렬

 

---

퀵 정렬에서 정렬 기준인 피벗에 따라 효율이 크게 달라집니다.

그렇기 때문에 피벗을 선택하는 것이 중요합니다.

 

방법 1

배열의 원수 수가 3개 이상이면, 배열에서 임의로 원소를 3개를 꺼내 중앙값인 원소를 피벗으로 선택합니다.

 

방법 2

방법 1을 발전시킨 방법으로, 배열의 맨 앞 원소, 중앙 원소, 맨 끝 원소를 정렬한 뒤에

 

 

원소 3개 정렬

 

중앙 원소와 끝에서 두 번째 원소를 교환합니다.

 

그리고 맨 앞 인덱스를 left, 맨 끝 인덱스를 right라고 했을 때

정렬 범위를 left + 1, right - 2로 해줍니다.

 

이렇게 하면 피벗을 정했을 때 어느 한 그룹의 원소가 많아지는 것을 피할 수 있습니다.

 

---

퀵 정렬의 시간복잡도는 O(n long n)입니다. 하지만 정렬하는 배열의 초깃값이나 피벗을 선택하는 방법에 따라 시간 복잡도가 증가하는 경우가 있고, 최악의 경우 시간 복잡도는 O(n^2)이 됩니다.

 

퀵 정렬은 원소 수가 많은 경우 효율적인 알고리즘입니다.

그래서 다음 코드는 원소 수가 9개 미만일 경우에는 단순 삽입 정렬을 하고

퀵 정렬을 할 경우 위에서 본 방법2를 사용하겠습니다.

 

def sort3(a, idx1, idx2, idx3):
    if a[idx2] < a[idx1]: a[idx2], a[idx1] = a[idx1], a[idx2]
    if a[idx3] < a[idx2]: a[idx3], a[idx2] = a[idx2], a[idx3]
    if a[idx2] < a[idx1]: a[idx2], a[idx1] = a[idx1], a[idx2]
    return idx2

def insertion_sort(a ,left, right):
    for i in range(left+1, right+1):
        j = i
        tmp = a[i]
        while j > 0 and a[j-1] > tmp:
            a[j] = a[j-1]
            j -= 1
        a[j] = tmp


def qsort(a, left, right):
    if right - left < 9:
        insertion_sort(a, left, right)
    else:
        pl = left
        pr = right
        m = sort3(a, pl, (pl+pr)//2, pr)    # 중앙값
        x = a[m]

        a[m], a[pr-1] = a[pr-1], a[m]   # 중앙값과 끝에서 두 번째 원소 바꿔줌
        pl += 1
        pr -= 2     # 정렬 범위 축소

        while pl <= pr:
            while a[pl] < x : pl += 1
            while a[pr] > x : pr -= 1
            if pl <= pr:
                a[pl], a[pr] = a[pr], a[pl]
                pl += 1
                pr -= 1

        if left < pr: qsort(a, left, pr)
        if pl < right: qsort(a, pl, right)


print('퀵 정렬(원소가 9개 미만일 경우 단순 삽입 정렬)')
num = int(input('원소 수 입력: '))
x = [None] * num

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

qsort(x, 0, len(x)-1)

print('오름차순 정렬')

print(''.join(str(x)))

 

sort3 함수는 중앙값을 리턴하는 함수고 insertion_sort 함수는 단순 삽입 정렬입니다.

qsort가 퀵 정렬로 원소 수가 9개보다 작으면 단순 삽입 정렬을 하고

그렇지 않으면 중앙값을 찾아 위에서 말한 방법2로 정렬을 진행합니다.

 

퀵 정렬