[알고리즘] 퀵 정렬 (Quick Sort)

Quick Sort

1. 피벗을 실행하여 배열에서 두 그룹으로 나눈다
2. 피벗 보다 작은 원소는 오른쪽에서 왼쪽으로, 피벗 보다 큰 원소는 왼쪽에서 오른쪽으로 이동한다.
3. 왼쪽 포인터와 오른쪽 포인터가 교체하는 지점에서, 왼쪽과 오른쪽 포인터 값을 교환한다
4. 그룹 내에서 새로운 피벗을 생성하고, 그 피벗을 기준으로 정렬이 마무리 될때까지 위 과정을 반복한다

퀵 정렬은 큰 문제를 작은 문제로 나누어 푸는 과정의 반복으로, 시간복잡도는 O(n log n)이다. 다만 매번 1개의 원소와 나머지 원소로 나뉘면 최악의 경우의 시간복잡도는 O(n^2) 이다. 원소 수가 적은 경우에는 다른 방식으로 정렬하는 것이 더 유리하다.

재귀적인 구현에서는 처음에 전체 배열을 재귀 함수의 매개변수로 전달하며, 각 단계에서 피벗을 기준으로 왼쪽 오른쪽을 나누어서 재귀 호출을 하는 방법이다. 비재귀적 구현에서는 명시적인 스택 방식을 채택해서 Push/Pop 연산으로 정렬할 배열의 범위를 관리한다.

1. 재귀적 구현
   • quick_sort(left), quick_sort(right) 같은 함수 호출을 반복.
   • 시스템의 재귀 호출 스택을 사용.
   • 깊이가 깊어지면 RecursionError 발생 가능. → 모든 배열을 스택에 넣기 위한 메모리 사용이 증가하기 때문
2. 비재귀적 구현
   • stack을 사용해서 분할 작업을 직접 관리. stack.append() / stack.pop()
   • 스택이 비어질 때까지 반복하면서 정렬 수행.
   • 메모리 절약 가능하고, RecursionError가 발생하지 않음.

재귀적인 Quick Sort 방식

배열에서 특정 요소를 피벗으로 선택한다. 일반적으로 첫번째/ 마지막 / 중간 요소 중 하나를 선택한다. 아래 예시에서는 중간 요소를 피벗으로 선택한 것을 기준으로 설명한다.

피벗을 기준으로 왼쪽에는 작은 값, 오른쪽에는 큰 값이 오도록 배열을 재배치하고, 정렬할 배열을 피벗을 중심으로 두 개의 배열로 나눈다.

피벗을 제외한 왼쪽 부분과 오른쪽 부분이 각각 정렬될때 까지 퀵 정렬을 수행한다.

def qsort(a:int, left:int, right:int) -> None:
    pl = left
    pr = right

    x = a[(left+right) //2]
    
    while pl <= pr :
        while a[pl] < x: pl += 1 # 왼쪽 -> 오른쪽
        while a[pr] > x: pr -= 1 # 오른쪽 -> 왼쪽
        if pl <= pr : #서로 자리 바꾸고 while 끝남
            print(f'  🔄 교환: a[{pl}] = {a[pl]} ↔ a[{pr}] = {a[pr]}')
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1

    if left < pr : qsort(a, left, pr) #왼쪽에 pr 보다 작은 값이 남아있으면 분할된 부분 다시 정렬
    if pl < right : qsort(a, pl, right) #오른쪽에 pl 보다 큰 값이 남아있으면 분할된 부분 다시 정렬
    
def quick_sort(a:int) -> None :
    qsort (a, 0, len(a)-1)

num = int(input('원소수 : '))
x = [None]*num

for i  in range(num):
    x[i] = int(input(f'원소수 입력 : '))

quick_sort(x)

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

#a는 x의 매개변수로 전달하여 리스트를 직접 수정할 수 있게함.
#매개변수로 전달하면 재귀 호출이 가능하고, 직접 수정할 수 있어 효율적임
#매개변수 = 파라미터 {name}. 인자 = argument "철수"

 

📌 예시

[ 3 6 1 9 7 2 5 ]

첫 번째 피벗 : 9

left : 3, 6, 1, 5, 7, 2 < 9 (피벗보다 작은 값으로 유지)

right : 5 < 9 와 교환

9는 정렬 완료로 고정

 

[ 3 6 1 5 7 2 9 ]

[0] ~ [5] 두 번째 피벗 : 5

left : 3 6 1 5 7 2 → 6 과 2 교환 → 3 2 1 5 7 2

5는 정렬 완료로 고정

 

[ 3 2 1 5 7 2 9 ]

left piv : 2

[0] ~ [2] 의 정렬 : 3과 1 교환

왼쪽 정렬 완료

 

[ 1 2 3 5 7 6 9 ]

[4] ~ [6] right piv : 6 → 7과 6 교환

 

[ 1 2 3 5 6 7 9 ] : 정렬 완료

비재귀적인 Quick Sort 방식

스택

나중에 들어온것이 먼저 나간다 (Last In First Out)

먼저 들어온것이 나중에 나간다 (First In Last Out)

스택에 데이터를 넣는다 Push, 스택에서 값을 뺀다 POP

Push 시 스택에 포인터가 하나씩 증가되고, POP 될때마다 스택 포인터가 하나씩 감소한다

from stack import Stack #stack.py에서 import
from typing import MutableSequence

def qsort(a:MutableSequence, left:int, right:int) -> None :
    range = Stack(right - left +1)
    range.push((left, right))
    
    while not range.is_empty():
        # 양 끝의 데이터를 pop 해서 배열의 길이의 중간값으로 인덱스를 설정. 배열을 둘로 나누는 과정
        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))

def quick_sort(a:int) -> None :
    qsort (a, 0, len(a)-1)

num = int(input('원소수 : '))
x = [None]*num

for i  in range(num):
    x[i] = int(input(f'원소수 입력 : '))

quick_sort(x)

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

 

📌 예제

[ 1 3 7 9 5 2 ]

초기 스택 : [(0, 5)] 처음부터 끝까지 설정

초기 피벗 : 중간값 7

 

[ 1 3 2 9 5 7 ]

2와 7이 교차하며 교환

왼쪽과 오른쪽을 각각 스택에 넣고 정렬을 진행. 정렬이 다 된 숫자는 pop. 스택에서 pop한 범위를 피벗 기준으로 정렬. 스택이 빌 때 까지 반복.

left piv : 3

1 3 2 → 1 2 3

right piv : 5

9 5 7 → 5 9 7 → 5 7 9 (7, 9가 교차하면서 교환)