Quick Sort
정렬 알고리즘 중 하나로 분할 정복(Divide and Conquer) 전략을 사용하는 알고리즘이다. C++ algorithm 헤더에 있는 sort함수는 퀵 소트로 구현되어 있고, 이러한 이유는 평균 수행시간이 빠르기 때문이다. (수행 시간에 대한 분석은 아래에 정리할 것이다.)
퀵 소트에서 중요한 부분은 피벗(pivot)과 파티션(partition)이고, 간단하게 피벗을 뽑고 파티션한다! 라고 생각할 수 있다.
피벗은 비교를 진행하기 위한 기준이 되는 원소를 말한다. 이 때 피벗은 가장 앞에 있는 원소로 선택할 수 있고 구현하는 방법에 따라 random하게 선택할 수도 있다. (여기서는 가장 앞에 있는 원소를 피벗으로 설정할 예정이다.)
다른 모든 원소들을 피벗과 비교하며 피벗보다 작은 L그룹, 피벗과 크기가 같은 E그룹, 피벗보다 큰 G그룹으로 나누는데 이 과정을 파티션이라고 한다. 그리고 L, E, G 그룹에 대해 각각 피벗을 뽑고 파티션을 진행한다. (Divide)
L, E, G그룹의 결과를 모두 합쳐주면 결과적으로는 모두 정렬된 상태를 돌려받을 수 있다. (Conquer)
그림을 통해서 위의 내용을 조금 더 자세하게 살펴보자.
막대 그래프의 크기를 오름차순으로 정렬하기 위해 퀵 소트를 사용하려고 한다. 이 중 빨간색 막대가 피벗이라고 가정하자. 모든 막대를 피벗과 비교하여 L, E, G 그룹으로 나눈다.
그러면 위의 그림과 같은 상태가 될 것인데 이 때 L, E, G 그룹으로 보면 오름차순으로 정렬된 것을 확인할 수 있지만 L, G그룹의 내부에서는 오름차순으로 정렬이 되지 않은 것을 확인할 수 있다. 그렇기 때문에 L, G그룹에 대해 다시 피벗을 뽑고 파티션을 진행하는 과정을 거쳐주어야 한다.
위와 같은 과정을 통해 퀵 소트를 구현하여 사용할 수 있지만 대개는 이런 방식을 사용하지 않는다. 더 좋은 방법이 존재하기 때문이다. 더 좋은 방법은 무엇일까? 한번 알아보도록 하자.
In-place Quick Sort
in-place라는 것은 입력으로 주어진 크기를 제외하고 추가로 사용하는 크기가 상수 크기 정도인 경우를 말한다.
이전에 설명한 방법은 L, E, G 라는 그룹을 새로 만들어 각각 해당하는 원소를 넣어주었기 떄문에 상수 크기보다 더 큰 크기를 사용했다. 그럼 어떻게 해야 in-place 구현이 가능한 것일까?
위와 같은 배열이 있다고 생각해보자. 피벗은 4로 선택할 것이다. 피벗을 뽑았으니 파티션을 진행해야 한다. 이 때의 파티션은 위에서 설명한 것과 다르다. Low를 가장 왼쪽 위치로 , High를 가장 오른쪽 위치로 세팅한다.
High가 Low보다 크면 아래의 1, 2, 3을 반복한다.
1. Low는 오른쪽으로 이동하면서 피벗과 비교를 진행한다. 만약 피벗보다 더 작으면 멈추지 않고 오른쪽으로 진행하며 비교를 계속한다. 만약 피벗보다 크거나 같다면 오른쪽으로 이동하는 것을 멈춘다.
2. High는 왼쪽으로 이동하면서 피벗과 비교를 진행한다. 만약 피벗보다 더 크면 멈추지 않고 왼쪽으로 진행하며 비교를 계속한다. 만약 피벗보다 작거나 같다면 왼쪽으로 이동하는 것을 멈춘다.
3. Low, High가 모두 멈추었을 때 High가 Low보다 크다면 두 위치의 값을 바꿔준다.
4. High가 Low보다 작다면 피벗과 High에 있는 값을 바꿔주고 파티션은 종료한다.
3은 4보다 작기 때문에 Low는 오른쪽으로 한 칸 이동하여 5를 가리킬 것이고 5는 4보다 크기 때문에 이동을 종료할 것이다. Low의 이동 결과는 위와 같은 그림이 될 것이다.
2는 4보다 작기 때문에 High는 이동을 하지 않는다. High의 이동 결과는 위와 같은 그림이 될 것이다.
Low와 High가 멈추었을 때 High가 Low보다 크기 때문에 두 위치의 값을 바꿔준다.
2는 4보다 작기 때문에 Low는 오른쪽으로 한 칸 이동하여 1을 가리킬 것이고 1역시 4보다 작기 때문에 Low는 오른쪽으로 한 칸 더 이동할 것이다. 5는 4보다 크기 때문에 이동을 종료할 것이다. Low의 이동 결과는 위와 같은 그림이 될 것이다.
5는 4보다 크기 때문에 High는 왼쪽으로 한 칸 이동하여 1을 가리킬 것이고, 1은 4보다 작기 때문에 High는 이동을 종료할 것이다. High의 이동 결과는 위와 같은 그림이 될 것이다.
이동이 종료된 시점에서 High가 Low보다 작기 때문에 피벗과 High의 값을 바꿔주는 것을 확인할 수 있다. 이렇게 파티션은 종료된다. 그리고 다시 퀵 소트를 실행하는데 이 때는 left ~ (High-1), (High+1) ~ right 범위에 대해 퀵 소트를 2번 호출한다.
Quick Sort C++ 코드
Quick Sort 분석
퀵 소트의 최악의 경우를 생각해보면 1개와 N-1개로 나누어지는 경우이다. 이 경우는 한 개의 최대(최소)의 원소를 선택하면 발생할 수 있다. 따라서 총 O(N)번 정도의 파티션이 필요하고 파티션은 O(N) 정도의 시간이 걸리기 때문에 최악 수행시간은 O(N^2)이 된다.
하지만 퀵 소트는 피벗을 랜덤으로 뽑기 때문에 발생할 확률이 굉장히 낮으며 평균 수행시간은 O(N(log N))으로 굉장히 빠르기 때문에 자주 사용된다.
+
질문이나 지적은 환영합니다ㅎㅎㅎ