[정렬] Quick Sort Algorithm depend on Pivot Selecting

Quick Sort Algorithm의 pivot 선택 방식에 대한 알고리즘 비교

 

1. 분석 목표 및 조건

Quick Sort Algorithm은 average-case time complexity Q(nlgn)을 가지는 알고리즘으로 알려져있다. 이에 대해 검증해보고, pivot selecting에 따른 Quick Sort Algorithm의 효율에 대해 분석해보겠다. Quick Sort Algorithm을 분석하기 전, 먼저 든 고민은 배열안의 수의 범위를 어디까지 한정해야하는 가였다. 배열의 수의 범위가 적다면 배열안에 중복의 숫자가 나올 확률이 늘어날 것이고, 이는 분명히 알고리즘의 효율에 영향을 끼칠 것이다. 또한, 수의 범위를 특정 숫자, 예를 들어 1~100이라고 가정한다면, 배열의 크기가 100인 배열과 5000인 배열안에서의 중복의 확률도 달라질 것이다. 나는 이번 분석에 중복이 많이 나올 확률은 피하되, 그 가능성은 열어둬 각 배열의 10배에 해당하는 숫자의 범위를 사용하였다. (예를 들어, 배열의 크기가 100이라면 숫자의 범위는 1~1000에 해당한다.) 또한, 모든 값은 1000번 반복의 평균 값이며, 1000개의 랜덤 배열을 사용하였다. 즉, 각 알고리즘을 비교함에 있어서, 같은 Sample을 사용하였다.

 

2. 비교 및 분석

우선 Quick Sort Algorithm의 average-case time complexity Q(nlgn)에 대한 검증을 위해, pivot item을 배열의 첫 번째 원소로 선택한 알고리즘의 결과에 대해 알아보겠다.

	comparison	exchange	time(ms)
100	634	411	2.988
200	1450	728	10.646
500	5244	3665	40.322
1,000	10451	5707	83.888
2,000	25020	14986	196.132
3,000	38412	20355	291.509
4,000	52238	27104	396.637
5,000	64098	34616	514.425

Quick Sort Algorithm (배열의 첫 번째 원소를 Pivot item으로 설정)

 

blue dot: comparison, yellow dot: exchange, green line:2nlgn, red line: 1/2nlgn

위 그래프로 알 수 있 듯,

1/2nlgn ≤ A(n) ≤ 2nlgn

A(n) ⊆ Θ(nlgn)

을 확인 할 수 있었다.

 

다음으론, pivot item selecting 방식에 따른 Quick Sort Algorithm 효율에 대해 살펴보겠다. 편의를 위해, 앞으로 A를 배열의 첫번째 원소를 pivot item으로 설정한 알고리즘, B를 배열의 원소에서 랜덤하게 pivot tiem을 설정한 알고리즘, C를 첫 번째, 중간, 마지막 원소 중 median에 해당하는 값을 pivot item으로 설정한 알고리즘으로 부르도록 하겠다. 이번 분석에 있어서는 코드 구현에 기반한 function call 비용이나, RISC, CISC 등 하드웨어 CPU적 특성에서 벗어나기 위하여, 실제 실행 시간이 아닌 comparison, exchange 수를 토대로 분석하겠다.

 

실험 결과를 보기에 앞서, 알고리즘 구현에 대한 설명을 하자면, Algorithm B는 랜덤으로 선택한 pivot을 원소의 첫번 째 원소와 자리를 바꾼 뒤,  Algorithm A를 실행함과 같다. Algorithm C는 첫번 째 원소와 중간에 위치한 원소, 마지막 원소의 median에 해당하는 원소를 첫번 째 원소에 위치하게 한 후, Algorithm A를 실행함과 같다.

 

이런 알고리즘의 특성을 보아, 실험 결과를 보기 전 나는 다음과 같은 추측을 하였다. Algorithm B는 랜덤하게 뽑힌 pivot item을 첫번 째 원소와 자리를 바꿔야하기 때문에, Algorithm A에 비해 한 번의 pivot selecting마다 하나의 exchange 비용을 소모하게 된다. 또한, 배열 자체가 랜덤하게 추출되었기 때문에, 첫번 째 원소를 pivot item을 선택하는 것과 배열 가운데 랜덤하게 하나의 원소를 pivot item을 선정하는 것은 아무런 확률적 차이가 없다. 이번 time complexity를 계산함에 있어, 고려하지 않을 요소지만 랜덤하게 원소를 선택한다는 행위 자체가 불필요한 비용을 더 소모하기 때문에 이 또한 Algorithm A에 비해 Algorithm B가 더 비효율적이라는 합리적인 추론을 할 수 있었다. Algorithm C는 pivot tiem을 선정함에 있어서, 첫번 째 원소, 중간 원소, 마지막 원소의 대소 비교를 해야하기 때문에 각 pivot selecting마다 세 번의 comparison이 더 필요하다. 또한, 구현 상 최소 0번에서 최대 3번의 exchange가 필요하다. 하지만 세 원소 중 median을 pivot item으로 설정했다는 것이 더 well-balanced한 sub array로 나눌 확률을 높여줘 최종 결과값은 다른 알고리즘보다 더 작은 것이란 추정 또한 가능하기 때문에 실행 결과를 보기까지 Algorithm A와 비교해 무엇이 더 효율적인지에 대한 추론이 불가능했다.

 

다음은 실행결과에 따른 그래프이다.

 

Number of Comparison (Algorithm A: blue dot, Algorithm B: yellow dot, Algorithm C: red dot)

세 알고리즘의 Comparsion 비교에서는 Algortihm C가 가장 좋은 결과값을 보였다. Algorithm C가 pivot item을 선정함에 있어서 세번의 비교가 더 필요하지만, 결론적으로는 더 well-balanced한 두 개의 subarray를 만든다는 것을 확인할 수 있었다. 이론 상, comparison에 있어 Algorithm A와 Algorithm B의 comparison의 횟수는 그저 운이기 때문에 두 알고리즘이 배열에 따라 대소 관계가 달라지는 결과를 보였다고 생각한다.

 

Number of Exchange (Algorithm A: blue dot, Algorithm B: yellow dot, Algorithm C: red dot)

 

exchange 횟수 비교에 있어서는, Algorithm A와 Algorithm C가 유의미한 차이를 보이지 못하였다. 같은 배열의 sample에서 comparison 값은 유의미한 차이를 냈음에도 즉, 더 well-balanced two sub array만들음에도 exchange 값에 큰 차이가 없는 것은 pivot item을 선정함에 있어 사용된 exchange 비용이 생각보다 크게 작용했다는 것을 알 수 있다. 하지만, 결론적으로는 Algorithm B와 Algorithm C의 exchange 횟수는 유의미한 차이가 없음을 알 수 있다.

 

3. 결론

 

다음과 같은 결과를 통해, worst algorithm은 Algorithm B라는 것을 알 수 있다. 이론적으로도, 실험을 통해서도 Algorithm B가 Algorithm A에 비해 합리적인 이유를 찾지 못하였다. 세 알고리즘 중 pivot selecting을 함에 있어 Algorithm C는 더 많은 cost를 사용하지만 결국 더 well-balanced한 sub array를 만들어 그 cost를 상회할 만큼 더 효율적이기 때문에, quick-sort를 사용할 때, 세 원소의 중위값을 사용하는 Algorithm C를 이용하는 것을 추천한다.

 

또한, 만약, 이미 정렬된 배열이 input으로 올 가능성(혹은 배열 안의 대부분의 원소가 이미 정렬 되어있을 확률)이 sorting 되어 있지 않은 배열이 input으로 올 가능성보다 더 높다면, 배열의 중간에 위치한 원소를 pivot item으로 설정하는 것이 좋은 pivot selecting이 될 수 있다고 생각한다. 중복이 많은 배열이 input으로 오는 경우는 quick sort를 사용하는 것 자체가 비합리적이라 생각하기 때문에 이는 논하지 않겠다.

 

 

참조)

	comparison	exchange	time(ms)
100	719	427	4.415
200	1420	938	12.032
500	4593	3276	44.855
1,000	12594	6782	97.928
2,000	22638	14109	218.583
3,000	37951	22828	331.376
4,000	57230	35558	462.782
5,000	72274	41812	592.024

Quick Sort Algorithm (Algorithm B)

 

 

	comparison	exchange	time(ms)
100	586	404	2.941
200	1327	824	9.998
500	4398	2936	37.010
1,000	9764	5511	82.191
2,000	22342	13419	183.401
3,000	34896	20469	292.354
4,000	47441	26305	396.347
5,000	61998	35786	515.165

Quick Sort Algorithm (Algorithm C)