알고리즘 - 퀵 정렬(1)

퀵 정렬은 가장 빠른 정렬 알고리즘으로 알려져 있으며 널리 사용됩니다.

 

퀵 정렬은 배열 어느 한 기준(피벗)으로 나누어 두 배열로 만들고

나누어진 배열에서도 기준(피벗)을 잡고 계속해서 두 배열로 나누어

모든 그룹에 원소 하나가 남으면 정렬이 완료됩니다.

 

PC가 기준이고 PL, PR은 각각 왼쪽, 오른쪽 커서입니다.

기준이 6이므로 왼쪽에는 6보다 작은 수, 오른쪽에는 6보다 큰 수를 이동시키면 됩니다.

먼저 5와 8은 정렬 시킬 필요가 없습니다.

다음으로 7과 9인데 둘 다 6보다 커서 정렬을 할 수 없습니다.

이럴 때는 PR이 정렬 가능한 수를 찾을 때까지 왼쪽으로 이동시켜 줍니다.

 

7과 3은 정렬 가능하므로 3과 7의 차리를 바꿔줍니다.

 

이번에는 1, 2 두 수 모두 기준인 6보다 큽니다.

6보다 같거나 큰 수를 찾기위해 PL을 계속 오른쪽으로 이동시킵니다.

 

PL이 6을 찾았고 6과 2의 자리를 바꿔줍니다.

 

다음으로 넘어가면 PR과 PL이 서로 교차되고

6을 기준으로 6이하인 배열과 6이상인 배열이 만들어졌습니다.

이런 식으로 배열 계속 기준으로 나누어 정렬하는 방법이 퀵 정렬입니다.

 

---

먼저 배열을 두 그룹으로 나누는 코드를 작성해보겠습니다.

 

def partition(a) -> None:
    n = len(a)
    pl = 0
    pr = n - 1
    pc = a[n//2]

    while pl <= pr: # pl의 인덱스가 더 커지면 종료
        while a[pl] < pc: pl += 1
        while a[pr] > pc: pr -= 1
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1

    print(f'기준은 {pc}입니다.')

    print(f'기준 이하의 그룹: {a[0 : pl]}')

    print(f'기준 이상의 그룹: {a[pr + 1 : n]}')


print('배열을 두 그룹으로 나누기')

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

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

partition(x)

 

첫 번째 while문은 서로 교차하면 종료되게 만든 것입니다.

두, 세 번째 while문은 pc보다 작은 pl값을, pc보다 큰 pr 값을 찾을 때까지 진행하게 만들었습니다.

그리고 조건문이 충족되면 서료 교환을 진행하고 현재 위치에서 각각 pl  + 1, pr - 1을 하게 했습니다.

 

결과

---

이제 위 코드에서 정렬된 그룹을 다시 기준으로 나누어 정렬시키면 퀵 정렬이 완성됩니다.

현재 위 결과에서 a[pr] = 5, a[pl] = 7인데, pr을 기준으로 그룹을 나누고

[1, 3, 2, 4, 5] 그룹에서 다시 기준을 잡아 그룹을 나누어 정렬

[7, 6, 8, 9] 그룹에서 다시 기준을 잡아 그룹을 나누어 정렬합니다.

 

def qsort(a, left, right) -> None:
    pl = left
    pr = right
    pc = a[(left + right) // 2]

    while pl <= pr: # pl의 인덱스가 더 커지면 종료
        while a[pl] < pc: pl += 1
        while a[pr] > pc: 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('퀵 정렬')

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를 재귀로 사용했습니다.

qsort 함수는 처음 사용했던 코드와 비슷하지만

pl과 pr을 left, right로 바꾸어 들어오는 값에 따라 바뀌게 했고

마지막에 if문을 추가해 계속해서 두 그룹으로 나누어 정렬을 진행하게 했습니다.

 

결과

 

 

 

비재귀적인 퀵 정렬은 다음 글에 이어서 하겠습니다.