6 - 6 퀵 정렬 & 6-7 병합정렬

퀵 정렬

일반적으로 사용되는 아주 빠른 정렬 알고리즘

피벗을 선택하여 나누기를 반복하며 모든 그룹이 1명씩 남으면 정렬이 완료된다.

피벗 : 그룹을 나누는 기준 

피벗을 어떤 값으로 선택하느냐에 따라 배열을 나누는 것과 정렬하는 성능에 영향을 미친다.

# 퀵 정렬 알고리즘 구현하기

from typing import MutableSequence

def qsort(a: MutableSequence, left : int, right: int) -> None:
    """a[left] ~ a[right]를 퀵 정렬"""
    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:
            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)

def quick_sort(a: MutableSequence) -> None:
    """퀵 정렬"""
    qsort(a, 0, len(a)-1)

if __name__ == "__main__":
    print('퀵 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num   
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    quick_sort(x)   # 배열 x를 퀵 정렬

    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')

 

배열 가운데에 있는 원소를 피벗으로 선택하고 배열을 두 그룹으로 나누는 과정을 반복하므로 재귀적이다.

 

비재귀적인 퀵 정렬 만들기

데이터를 임시 저장하기 위해 스택을 사용한다.

일반적으로 원소 수가 적은 배열일수록 나누는 과정을 빠르게 마칠 수 있다.

원소 수가 많은 그룹의 나누기를 나중에 하고 원소 수가 적은 그룹의 나누기를 먼저 하면 스택에 동시에 쌓이는 데이터의 개수가 적어지기 때문이다.

# 비재귀적인 퀵 정렬 구현하기

from stack import Stack
from typing import MutableSequence

def sort(a : MutableSequence, left : int, right: int) -> None:
    """a[left] ~ a[right]를 퀵 정렬 (비재귀적인 퀵 정렬)"""
    range = Stack(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))  # 오른쪽 그룹의 커서를 저장

퀵정렬의 시간 복잡도

퀵정렬은 배열을 조금씩 나누어 보다 작은 문제를 푸는 과정을 반복하므로 시간복잡도가 O(nlogn)이다.

하지만 배열의 초깃값이나 피벗을 선택하는 방법에 따라 실행 시간 복잡도가 증가하는 경우가 있어 , 최악의 경우 O(n2)이다.

 

 

병합 정렬

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

나눈 두 배열을 각각 정렬을 마친 후, 각 두 배열에서 주목하는 원소의 값을 비교해 작은쪽의 원소를 꺼내 새로운 배열에 저장한다. 이 작업을 반복하여 정렬을 마친다.

 

# 정렬을 마친 두 배열을 병합하기

from typing import Sequence, MutableSequence
def merge_sorted_list(a:Sequence, b:Sequence, c:MutableSequence) -> None:
    """정렬을 마친 배열 a와 b 를 병합하여 c에 저장"""
    pa, pb, pc = 0,0,0   # 각 배열의 커서
    na, nb, nc = len(a),len(b),len(c)   # 각 배열의 원소 수
    
    while pa < na and pb < nb:   # pb와 nb를 비교하여 작은 값을 pc에 저장
        if a[pa] <= b[pb]:
            c[pc] = a[pa]
            pa += 1
        else:
            c[pc] = b[pb]
            pb += 1
        pc += 1
    
    while pa <na:  # a 에 남은 원소를 c에 복사
        c[pc] = a[pa]
        pa += 1
        pc += 1

    while pb<nb:  # b 에 남은 원소를 c에 복사
        c[pc] = b[pb]
        pb += 1
        pc += 1

if __name__ == '__main__':
    a = [2,4,6,8,11,13]
    b = [1,2,3,4,9,16,21]
    c = [None] *( len(a) + len(b))
    print('정렬을 마친 두 배열의 병합을 수행합니다.')

    merge_sorted_list(a,b,c)   # 배열 a와 b를 병합하여 c에 저장

    print('배열 a와 b를 병합하여 배열 c에 저장했습니다.')
    print(f'배열 a:{a}')
    print(f'배열 b:{b}')
    print(f'배열 c:{c}')