[CLRS] [7-1] Description of quicksort (퀵정렬 구현)

0. Intro

- 이번 7 챕터에서는 quicksort, 퀵정렬에 대해서 알아보고자 한다.

 

1. Quicksort(퀵정렬)

- quicksort(퀵정렬)은 2-3에서 배웠던 mergesort(병합정렬)과 비슷하다.

- divide-and-conquer(분할정복)알고리즘을 이용한다.

- 평균적으로 매우 빠른 수행 속도를 보여주기 때문에 quicksort 라고 불린다.

 

2. Quicksort의 알고리즘 

- QuickSort의 핵심은 분할(divide)하는 과정이다. 

- QuickSort는 배열을 작은 부분으로 쪼개서 정렬하는 방식으로 작동하며, 다음과 같은 과정을 거친다.

 

i) Pivot 선택
- 배열에서 임의의 기준이 되는 Pivot 요소를 선택한다.

- Pivot을 선택하는 방식은 크게 4가지가 존재한다.

 

a) 첫 번째 요소를 Pivot으로 채택

- [1,2,3,4,5] 이런식으로 정렬된 배열에서 최악의 성능을 낸다.

 

b) 마지막 요소를 Pivot으로 채택

- 이 역시, 정렬된 배열에서 최악의 성능을 낸다.

 

c) 배열의 중간 요소를 Pivot으로 채택

 

d) 무작위로 Pivot을 채택

- 정렬된 배열에서도 평균적인 성능을 유지한다.

- Quicksort가 최악의 성능을 피할 수 있게 해주는 좋은 방법이다.

 

ii) divide(분할)

- 배열의 요소를 Pivot을 기준으로 두 그룹으로 나눈다.

a) pivot보다 작은 데이터들은 pivot의 왼쪽에 배치

b) pivot보다 큰 데이터들은 pivot의 오른쪽에 배치

 

iii) conquer

- pivot을 기준으로 나뉜 두 부분에 대해 i),ii)을 재귀적으로 수행

 

해당 과정들이 반복되면서 모든 요소가 정렬되게 된다.

 

3.QuickSort Code(Python)

- Quicksort(퀵정렬)을 파이썬으로 구현해보자.

def quicksort(arr):
    if len(arr)<=1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    pivot = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quicksort(left) + pivot + quicksort(right)

- 사실 해당 코드는 효율적인 Quicksort라고 볼 순 없으나,
- 가장 이해하기 쉽게 작성되었기에 Quicksort에 대해 쉽게 이해할 수 있다.

 

다음 챕터(7-2)에서 QuickSort의 시간복잡도를 알아보자.