[Algorithms] 퀵 정렬(Quick Sort)

깃허브: https://github.com/PSLeon24/DataStructure/blob/main/Sorting%20algorithm.ipynb

퀵 정렬(Quick Sort)

퀵 정렬(quick sort)은 가장 빠른 정렬 알고리즘으로 알려져 있고 현재 널리 사용되고 있음
퀵 정렬을 고안한 사람은 찰스 A. R. 호어(Charles Antony Richard Hoare)로 정렬 속도가 매우 빨라 Quick Sort라고 이름을 붙임
퀵 정렬에서는 그룹을 나누는 기준인 피벗(pivot, 중심축)이 중요한 역할을 함

https://dev.to/robogeek95/a-visual-giude-on-quicksort-algorithm-55df

Algorithm

일반적으로 가장 심플한 퀵 정렬은 위 이미지와 같이 배열의 가장 첫 번째 원소를 pivot으로 삼아서 가장 첫 원소의 다음 원소부터 오른쪽으로 스캔하며 피벗보다 큰 데이터(pl)를 찾고, 마지막 원소부터 왼쪽으로 스캔해서 피벗보다 작은 데이터(pr)를 찾는다. 
pl이 pr보다 왼쪽에 있을 경우, 두 개의 data를 swap한다. 이 과정을 반복하며 pl이 pr보다 오른쪽에 있을 경우, 즉 pl과 pr이 교차하는 경우 pr(작은 값)과 피벗을 swap한다. 이렇게 swap된 피벗은 해당 위치에 fix되며 피벗을 기준으로 왼쪽과 오른쪽으로 그룹을 나누어 해당 과정을 반복한다. 마지막으로 전체를 결합하면 정렬된 배열이 완성된다.

 

핵심: 분할, 정복, 결합
 
글로는 이해가 어려울 수 있으니 예제를 보며 학습해보도록 하자.
Quick Sort Example
Q. [35, 42, 16, 27, 89, 10, 99, 5, 63] 와 같이 데이터가 있을 때 퀵 정렬을 이용해 정렬하고 피벗의 순서를 작성해보자.

먼저 주어진 배열에서 가장 첫 번째 원소인 35를 피벗(pivot)으로 설정한다.
그 후 배열의 시작부터 오른쪽으로 탐색(scan)하며 피벗보다 큰 값을 찾는다(pl). 그리고 배열의 마지막부터 왼쪽으로 탐색하며 피벗보다 작은 값을 찾는다(pr). 이 과정을 진행하면 피벗보다 큰 값은 42이고, 피벗보다 작은 값은 5이다. 둘의 값을 교환(swap)한다.
그 후 pl과 pr의 위치부터 시작하여 다시 위 과정을 반복하면 피벗보다 큰 값은 89이고, 작은 값은 10이다. 둘의 값을 교환한다.
교환을 마치고 나면 pl과 pr값이 교차한다. 이렇게 되면 pr값인 10과 35를 교환한다. 피벗과 작은 값(pr)이 교환되는 경우 피벗은 교환된 위치에 고정(fix)한다.
그러면 현재까지 정렬된 배열은 [10, 5, 16, 27, 35, 89, 99, 42, 63]과 같다.
이제 35(고정된 피벗)을 기준으로 왼쪽과 오른쪽으로 그룹을 나눠 해당 과정을 반복한다.
다시 풀어서 설명하면 [10, 5, 16, 27]과 [89, 99, 42, 63]으로 나누어 퀵 정렬을 진행하면 된다.
[10, 5, 16, 27]부터 퀵 정렬을 수행하면, 10이 첫 pivot이 된다.
배열의 시작부터 오른쪽으로 탐색을 진행하여 피벗인 10보다 큰 값은 16이 되고 배열의 마지막부터 왼쪽으로 탐색하여 피벗인 10보다 작은 값은 5이다. 이 경우 pl과 pr이 교차하는데 이럴 경우 두 값을 교환하지 않고 pr과 피벗을 교환해주고 교환된 피벗은 해당 위치에 고정(fix)된다.
[5, 10, 16, 27] 이후 5를 피벗으로 설정하고 다시 탐색 과정을 진행한다.
이 경우 이미 고정된 10은 skip하고 탐색을 진행할 때, 5보다 큰 값인 16은 있으나 5보다 작은 값이 없으므로 5는 해당 위치에 고정된다.
[5, 10, 16, 27] 이후 16을 피벗으로 설정하고 다시 탐색 과정을 진행한다.
이 경우에도 16보다 큰 값인 27은 있지만 작은 값이 없으므로 16은 해당 위치에 고정된다.
[5, 10, 16, 27] 27의 경우 마지막으로 탐색해야 할 값이므로 해당 위치에 자연스럽게 고정된다.
[5, 10, 16, 27]
이 과정이 끝나면 이제 피벗을 기준으로 오른쪽 값을 정렬해주면 된다.
[89, 99, 42, 63]
먼저 89를 피벗으로 설정하고 배열의 시작부터 오른쪽으로 피벗보다 큰 값을 찾으면 99가 있으며, 배열의 끝부터 왼쪽으로 피벗보다 작은 값을 찾으면 63이 있다. 두 값을 교환(swap)한다.
[89, 63, 42, 99] 그리고 현재 pl과 pr의 위치부터 다시 탐색을 시작하면 피벗보다 큰 값은 99(pl)이고, 작은 값은 42(pr)인데 pl과 pr이 교차되었으므로 피벗인 89와 pr인 42 교환(swap)하고 교환된 피벗은 해당 위치에 고정된다.
[42, 63, 89, 99] 이후 42를 피벗으로 설정하고 탐색 과정을 진행하면 피벗보다 큰 값은 오른쪽으로 탐색할 때 존재하나, 작은 값이 존재하지 않으므로 피벗인 42는 해당 위치에 고정된다.
[42, 63, 89, 99] 이후 63을 피벗으로 설정하고 탐색 과정을 진행해도 마찬가지이다.
[42, 63, 89, 99] 이후 99는 마지막으로 탐색해야 할 값이므로 해당 위치에 자연스럽게 고정된다.
[42, 63, 89, 99]
이 과정을 다 마치면 정렬이 끝난다.
정렬 결과를 보면 [5, 10, 16, 27, 35, 42, 63, 89, 99]와 같이 잘 정렬 되었음을 확인할 수 있다.
피벗의 순서는 다음과 같다.
35 → 10 → 5 → 16 → 27 → 89 → 42 → 63 → 99 (볼드체 처리한 부분 확인)
 
이제 다른 예제도 확인해보자.

앞서 설명한 예제와 동일한 방식으로 logic이 진행되니 참고하며 직접 해결해보자.
혹여나 학습 도중에 어려움이 생길 경우 댓글을 남기면 필자가 최대한 답변을 남기도록 하겠다.
 
자, 그러면 이를 코드로 어떻게 작성할 수 있을까?

파이썬 실습

나누는 과정 다 출력하기

지금까지 학습한 모든 정렬 코드는 아래의 깃허브에 올려두었다.
https://github.com/PSLeon24/DataStructure/blob/main/Sorting%20algorithm.ipynb