[자료구조와 함께 배우는 알고리즘][정렬 알고리즘] - 퀵 정렬

퀵 정렬(Quick sort)은 가장 빠른 정렬 알고리즘으로 알려져 있고 또한 널리 사용된다.

 

배열을 두 그룹으로 나누기

5

7

1

4

6

2

3

9

8

      pl                                                                   x                                                                     pr    

 

그룹을 나누려면 피벗 이하인 원소를 배열 왼쪽(맨 앞쪽)으로, 피벗 이상인 원소를 배열 오른쪽(맨 뒤쪽)으로 옮겨주어야 한다. 

a[pl] >= x가 성립하는 원소를 찾을 때까지 pl을 오른쪽 방향으로 스캔한다.
👉 왼쪽에서부터 시작해서 피벗보다 큰 값을 찾는 과정
a[pr] >= x가 성립하는 원소를 찾을 때까지 pr을 왼쪽 방향으로 스캔한다.
👉 오른쪽에서부터 시작해서 피벗보다 작은 값을 찾는 과정

5

7

1

4

6

2

3

9

8

----------------->   pl                                                                                   pr   <-----------------------------

 

 

5

3

1

4

6

2

7

9

8

----------------------------------------------------------->   pl                pr   <---------------------------------------------

 

 

5

3

1

4

2

6

7

9

8

피벗 이하인 그룹: a[0] ~ a[pl-1]
피벗 이상인 그룹: a[pr+1] ~ a[n-1] 

위의 예시는 피벗이 일치하지 않은 경우인데 만약 피벗으로 잡은 원소가 실제 퀵정렬 작업을 할 때 중앙에서 pl, pr이 만나게 되는 경우라면 피벗이 일치하는 경우입니다.

 

< 퀵 정렬을 사용해서 배열을 두 그룹으로 나눈 구현 코드 >

# 배열을 두 그룹으로 나누기

from typing import MutableSequence

def partition(a):
    n = len(a)
    pl = 0
    pr = n-1
    x = a[n//2] #가운데 원소 피벗

    while pl<=pr:
        while a[pl] < x:
            pl+=1
        while a[pl] < x:
            pr-=1
        #피벗기준 왼쪽은 피벗보다 큰거 만나면 멈춰서 if문으로 확인
        #피벗기준 오른쪽은 피벗보다 작은 거 만나면 멈춰서 if문으로 확인해준다.
            
        if pl <= pr:
            #피벗기준으로 나눈 pl pr을 살펴보는 도중 pr이 작고 pl이 큰 경우 두 수를 바꿔준다.
            a[pl],a[pr] = a[pr],a[pl]
            pl += 1
            pr -= 1

 

 

< 퀵 정렬 알고리즘 구현하기 >

# 퀵 정렬 알고리즘 구현하기
from typing import MutableSequence

def qsort(a,left,right):
    n = len(a)
    pl = 0
    pr = n-1
    x = a[n//2] #가운데 원소 피벗

    while pl<=pr:
        while a[pl] < x:
            pl+=1
        while a[pl] < x:
            pr-=1
        #피벗기준 왼쪽은 피벗보다 큰거 만나면 멈춰서 if문으로 확인
        #피벗기준 오른쪽은 피벗보다 작은 거 만나면 멈춰서 if문으로 확인해준다.
            
        if pl <= pr:
            #피벗기준으로 나눈 pl pr을 살펴보는 도중 pr이 작고 pl이 큰 경우 두 수를 바꿔준다.
            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)