728x90
퀵 정렬 partition함수에 대한 각기 다른 코드를 분석해보겠습니다.
partition함수는 배열과 left, right인덱스를 받아 한 단계의 퀵정렬을 수행한 후 피봇인덱스를 반환합니다.
일단 가장 쉬운 방법입니다.
1. Algorithm Partition(arr, left, right)
2. Input: 정렬할 배열, 맨 왼쪽 인덱스, 맨 오른쪽 인덱스
3. Output: high(피봇의 현재 인덱스)
4. pivot <- arr[left]
5. low <- left + 1
6. high <- right
7. while (low <= high) do {
8. while (pivot >= arr[low] and low <= right) do
9. low++;
10. while (pivot <= arr[high] and high >= left+1) do
11. high--;
12. if (low <= high)
13. Swap(arr, low, high);
14. }
15. Swap(arr, left, high)
16. return highpivot >= arr[low] 라는 기본적인 연산 뒤에 마지노선으로
low <= right,
high >= left+1
을 적어줬습니다.
즉, low는 right의 바로 옆 인덱스까지가 최대이고,
high는 pivot이 있는 left 인덱스까지가 최대입니다.
다음은 이걸 조금 개선한 코드입니다.
1. Algorithm Partition(arr, left, right)
2. Input: 정렬할 배열, 맨 왼쪽 인덱스, 맨 오른쪽 인덱스
3. Output: high(피봇의 현재 인덱스)
4. pivot <- arr[left]
5. low <- left + 1
6. high <- right
7. while (low <= high) do {
8. while (pivot < arr[high]) do
9. high--;
10. while (pivot >= arr[low] and low <= high) do
11. low++;
12. if (low <= high) {
13. Swap(arr, low, high);
14. low++;
15. high--;
16. }
17. }
18. Swap(arr, left, high)
19. return high
8번 줄에서 while문은 high가 피봇인덱스와 같은 경우 멈추기 때문에, 어떤 상황이어도 high는 최대 피봇까지만 갈 수 있습니다.
그리고 high와 low가 교차되면 퀵정렬 한 단계가 끝나고, low는 필요없기 때문에(high와 left를 swap하니까요)
10번 줄에서 low는 최대 high바로 옆까지만(교차되는 순간까지만) 갈 수 있도록 마지노선을 정해줬습니다.
즉, high와 low가 교차되는 순간 low의 수행을 멈추는 것입니다. 이렇게 하면 수행시간이 줄어들겠죠?
(high를 지났는데도 계속 비교를 수행하는 것 방지)
위의 코드의 출저는 열혈 자료구조(윤성우)이고,
아래코드의 출처는 PBL방식으로 배우는 자료구조(김영학) 책입니다.
728x90
