알고리즘 | 정렬 기법 | 퀵 정렬 (Quick Sort)

Quick sort는 1961년 Tony Hoare(토니 호어)가 발표한 정렬 기법이다.

 

정렬 기법 중에서 매우 흔히 사용되는 기법으로, 현대에는 Quick Sort에 여러 가지 최적화 기법을 추가한 변형을 자주 사용한다. 

 

예를 들어, Java의 Array.sort() 메서드는 기본형 타입의 배열(int, long 등)에 대해서는 Dual-Pivot Quick Sort를 사용한다고 한다.

(객체 배열에 대해서는 Tim Sort를 사용한다.)

- Dual-Privot Quick Sort: Insertion Sort와 Quick Sort를 결합한 정렬 기법

- Tim Sort: Insertion Sort와 Merge Sort를 결합한 정렬 기법

 

---

 

1. 핵심 아이디어

분할 정복 전략을 사용하여 리스트를 정렬한다. 

출처: https://aquarchitect.github.io/swift-algorithm-club/Quicksort/

1) 기준이 되는 피벗(pivot) 요소를 선택한다.

2) 피벗 대비 작은 요소(left)와 큰 요소(right)로 양분한다. (피벗과 동일한 값은 mid로 저장)

3) 각 부분에 이 동작을 재귀적으로 반복한다. 

 

2. 코드를 통한 이해

책과 인터넷 자료를 참고해서 두 가지 버전으로 Quick Sort를 구현해보았다. 

실제 동작하는지 여부는 백준 2750번 (수 정렬하기) 문제를 통해서 확인했다. (https://www.acmicpc.net/problem/2750)

 

1) 이해를 위한 쉬운 버전

이해를 위한 쉬운 버전으로, 위 이미지와 똑같이 동작하는 코드이다. 

Quick Sort의 개념을 이해하는 데 있어서는 이 코드 예시가 좋은 것 같다. 

# 퀵 소트 구현해보기 1
# 서브 리스트로 나누어 구현 
'''
이해를 위한 쉬운 ver. 
재귀 개념을 더 적극 활용하였고, 퀵 소트의 개념 이해에 도움이 되는 코드이다. 
'''


nums = []
for i in range(int(input())):
    nums.append(int(input()))

def quick_sort(nums):
    # base case: 리스트 길이가 1 이하가 되면 더 이상 정렬할 게 없으므로 return
    if len(nums) <= 1:
        return nums
    
    # pivot 선택 - 가운데 인덱스를 기준으로 하는 이유: 최악의 경우(이미 정렬된 리스트)에 더 안정적인 성능
    pivot = nums[len(nums)//2]

    # 분할하기
    left, mid, right = [], [], []
    for num in nums: # nums의 요소들을 훑으면서 pivot을 기준으로 분류
        if num < pivot: 
            left.append(num)
        elif num > pivot:
            right.append(num)
        else:
            mid.append(num)

    # 재귀적으로 left, right 서브 리스트를 정렬한 후, 병합
    return quick_sort(left) + mid + quick_sort(right)


nums = quick_sort(nums)
for num in nums:
    print(num)

 

pivot을 nums[:-1]로 지정하기도 하던데, 그렇게 할 경우 최악의 경우 O(n^2)의 시간 복잡도를 가지게 된다. (리스트가 이미 정렬되어 있는 경우) pivot을 가운데 인덱스로 지정할 경우, 이미 정렬되어있는 리스트에서도 안정적인 성능을 보이게 된다. 

 

 

2) 더 효율적인 버전 (교과서 ver.)

# 퀵 소트 구현해보기 2
# 포인터 개념 활용 

'''
더 효율적인 ver. 
앞선 코드 대비 장점은 인플레이스(in-place)로 분할을 수행한다는 점.
즉, 추가적인 메모리를 사용하지 않고 입력 리스트 내에서만 작업을 수행함. 
첫번째 코드와 달리 리스트를 새로 만드는 메모리가 소요되지 않음. 

즉, 공간 복잡도 측면에서 우위에 있음.
'''

nums = []
for i in range(int(input())):
    nums.append(int(input()))

def quick_sort(nums, left, right):
    # 양쪽 포인터를 양 끝으로 설정
    pl, pr = left, right
    
    # pivot 선택 - 가운데 인덱스를 기준으로 하는 이유: 최악의 경우(이미 정렬된 리스트)에 더 안정적인 성능
    pivot = nums[(left + right) // 2] 
    
    # 분할하기
    while pl <= pr: # pl과 pr이 교차할 때까지 
        while nums[pl] < pivot: 
            pl += 1 # pl을 오른쪽으로 이동. 코드를 반복하다보면 pivot 보다 큰 값에서 포인터는 멈추게 된다. 
        while nums[pr] > pivot:
            pr -= 1 # pl을 왼쪽으로 이동. 코드를 반복하다보면 pivot 보다 작은 값에서 포인터는 멈추게 된다. 
        
        # 아직 교차하지 않았다면
        if pl <= pr: 
            nums[pl], nums[pr] = nums[pr], nums[pl] # 양쪽 값의 위치를 교환
            pl, pr = pl+1, pr-1

    # 분할된 왼쪽, 오른쪽 부분에 대해서 재귀적으로 퀵 정렬
    if left < pr:
        quick_sort(nums, left, pr)
    if pl < right:
        quick_sort(nums, pl, right)


quick_sort(nums, 0, len(nums)-1)
for num in nums:
    print(num)

 

이 코드 예시는 교과서에서 소개하고 있는 방법이다. 

별도의 리스트를 새로 할당받지 않으므로 메모리 측면에서 이점이 있다. 즉, 공간 복잡도 측면에서 유리하다.

 

개인적으로 마지막 재귀 부분이 잘 이해가 되지 않았는데, 

    # 분할된 왼쪽, 오른쪽 부분에 대해서 재귀적으로 퀵 정렬
    if left < pr:
        quick_sort(nums, left, pr)
    if pl < right:
        quick_sort(nums, pl, right)

if 조건이 굳이 왜 필요한가에 대해서 알 수 없었다. 

알아낸 답에 대해서 적자면, 

 

분할 작업이 끝나면 pl(왼쪽 포인터)과 pr(오른쪽 포인터)이 서로 교차된 상태이다. 

즉, 인덱스 기준으로 보면 left … pr | pl … right 형태이다.

 

여기서 고려해야 할 예외 사항이 바로 저 if문에 해당한다.

- 만일 pr이 left보다 작다면, 'left ... pr' 부분은 비어있는 셈이다. 따라서 해당 서브 리스트에 대해서는 재귀를 들어갈 필요가 없다.

- 마찬가지로 pl이 right보다 크다면, 'pl ... right' 부분이 비어있는 셈이다. 따라서 재귀에 들어갈 필요가 없다. 

 

효율성을 위한 조치인 셈이다. 

 

 

3. 시간 복잡도

• 최악의 경우: O(n2)
• 최선의 경우: O(nlogn)