퀵 정렬(Quick Sort)이란?
- 교환 정렬의 일종이며 분할 정복법에 근거합니다.
- 축값을 기준으로 정렬하는데, 축값을 중심으로 축값보다 큰 값은 오른쪽 리스트에, 작은 값은 왼쪽리스트에 이동시킵니다.
- 오른쪽 리스트와 왼쪽 리스트 부분은 독립적인 단위로 정렬하여 오른쪽 리스트부분에 대한 새로운 분할 축값을 선택하여 두 부분을 분리하고, 왼쪽 리스트부분 역시 새로운 축값을 선택하여 두 부분으로 분리하는 과정을 반복하는데 리스트들은 재귀적 방법으로 각각 재배열 하는 방식입니다.
- 각 분할 자료개수가 1이 되면 정렬은 완료됩니다.
예시
쉬운 이해를 위해서 다음과 같이 1부터 7까지 총 7개의 숫자가 들어있는 배열을 기준으로 설명하겠습니다.
1 | [1, 6, 7, 4, 5, 2, 3] |
항상 정 가운데를 기준으로 분할을 하는 병합 정렬과 달리, 퀵 정렬은 흔히 피봇(pivot)이라고 불리는 임의의 기준 값을 사용합니다.
pivot 값을 선택하는데는 여러가지 방법이 있지만 여기서는 간단한 설명을 위해 정 중앙에 위치한 4를 pivot으로 정하겠습니다. 다음과 같이 이 pivot값을 기준으로 pivot보다 작은 값의 그룹과 pivot보다 큰 값의 그룹으로 나눕니다.
1 | [3, 2, 1] < 4(p) < [7, 5, 6] |
위와 같이 pivot값보다 작은 값들은 모두 왼편으로 몰고, 큰 값들은 모두 오른편으로 몰면 기준값은 정확히 정렬 된 위치에 놓이게 됩니다.
또한 이런 방식으로 분할을 해 놓으면 앞으로 더 이상 왼편에 있는 값들과 오른편에 있는 값들 간에는 비교를 할 필요가 없습니다.
따라서 반대편은 전혀 신경쓰지 않고 왼편이든 오른편이든 같은편 내의 값들 끼리만 비교 후 정렬을 할 수 있게 됩니다.
먼저 왼편을 동일한 방식으로 정렬해보도록 하겠습니다.
1 | [1] < 2(p) < [3] |
오른편도 동일한 방식으로 정렬해보겠습니다.
1 | [] < 5(p) < [7, 6] |
오른편에 값이 두개가 있기 때문에 추가 정렬이 필요합니다. 왼편에는 값이 없지만 오른편에는 여전히 두 개 의 값이 있기 때문에, 동일한 방식의 정렬을 적용하겠습니다.
1 | [6] < 7(p) < [] |
마지막으로 지금까지 좌우로 분할했던 값들을 모두 합쳐보면 다음과 같이 정렬된 배열을 얻을 수 있습니다.
1 | [1, 2, 3, 4, 5, 6, 7] |
특징
- 파이썬의 list.sort()함수처럼 프로그래밍 언어 차원에서 기본적으로 지원되는 내장 정렬 함수는 대부분의 퀵 정렬을 기본으로 합니다.
- 일반적으로 원소의 개수가 적어질수록 나쁜 중간값이 선택될 확률이 높아지기 때문에, 원소의 개수에 따라 퀵 정렬에 다른 정렬을 혼합해서 쓰는 경우가 많습니다.
- 병렬 정렬과 퀵 정렬은 분할 정복과 재귀 알고리즘을 사용한다는 측면에서는 유사해보이지만, 내부적으로 정렬을 하는 방식에는 큰 차이가 있습니다.
- 병렬 정렬은 항상 정 중앙을 기준으로 단순 분할 후 병합 시점에서 값의 비교 연산이 발생하는 반면, 퀵 정렬은 분할 시점부터 비교 연산이 일어나기 때문에 그 이후 병합에 들어가는 비용이 매우 적거나 구현 방법에 따라서 아예 병합을 하지 않을 수도 있습니다.
복잡도
- 퀵 정렬의 성능은 어떻게 pivot값을 선택 하느냐에 크게 달라질 수 있습니다. 이상적인 경우는 pivot값을 기준으로 동일한 개수의 작은 값들과 큰 값들이 분할되어 병합 정렬과 마찬가지로 O(NlogN)의 시간 복잡도를 가지게 됩니다.
- 하지만 pivot값을 기준으로 분할했을 때 값들이 한 편으로 크게 치우치게 되면, 퀵 정렬의 성은은 저하되게 되며, 최악의 경우 한 편으로만 모든 값이 몰리게 되어 O(N^2)의 시간 복잡도를 보이게 됩니다.
- 따라서 상용 코드에서는 중앙값(median)에 가까운 pivot값을 선택할 수 있는 섬세한 전략이 요구되며, 배열의 첫값과 중앙값 그리고 마지막값 중에 크기가 중간인 값을 사용하는 방법이 많이 사용됩니다.
- 퀵 정렬의 곤간 복잡도는 구현 방법에 따라 달라질 수 있는데, 입력 배열이 차지하는 메모리만을 사용하는 in-place sorting방식으로 구현을 사용할 경우, O(1)의 공간 복잡도를 가진 코드의 구현이 가능합니다.
1 | def quick_sort(arr): |
2 | if len(arr) <= 1: |
3 | return arr |
4 | pivot = arr[len(arr) // 2] |
5 | lesser_arr, equal_arr, greater_arr = [], [], [] |
6 | for num in arr: |
7 | if num < pivot: |
8 | lesser_arr.append(num) |
9 | elif num > pivot: |
10 | greater_arr.append(num) |
11 | else: |
12 | equal_arr.append(num) |
13 | return auick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr) |
먼저 리스트의 정 가운데 있는 값을 pivot값으로 선택하고, pivot값보다 작은 값, 동일한 값 그리고 큰 값을 담아둘 3개의 리스트를 생성합니다.그리고 반복문을 통해 각 값을 pivot과 비교 후에 해당 리스트에 추가시킵니다.그 다음 작은 값과 큰 값을 담고 있는 배열을 대상으로 퀵 정렬 함수를 재귀적으로 호출합니다. 마지막으로 재귀 호출의 결과를 다시 크기 순으로 합치면 정렬된 리스트를 얻을 수 있습니다.