퀵정렬 자료구조 코드분석(슈도코드)

퀵 정렬 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 high

pivot >= 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방식으로 배우는 자료구조(김영학) 책입니다.