퀵소트

퀵 소트 알고리즘

 

간략한 퀵소트 알고리즘 

    pivot을 선택하여 pivot보다 작은 것을 오른쪽으로 큰 것을 왼쪽으로 보낸뒤

    pivot의 자신의 자리로 들어간 뒤에

    앞쪽 배열과 뒤쪽 배열을 재귀적으로 퀵소트를 호출하는 방법을 사용한다.

 

 

퀵 소트 알고리즘의 pseudo-code(의사코드)의 예

 

1. pivot을 선택한다. (다양한 방법이 있고 이에 따라 성능이 많은 차이를 지니게 된다.)

2. pivot을 배열의 맨 앞(혹은 맨 끝)의 요소와 교체한다.

3. i = 1로 설정,j=asize-1 로 설정

4. Loop i가 j보다 작을 동안

    4.1 Loop pivot(배열의 맨 앞의 요소) >= 배열의 i번째 요소

         4.1.1 i를 증가

    4.2 Loop pivot(배열의 맨 앞의 요소) <= 배열의 j번째 요소

         4.2.1 j를 감소

    4.3 i가 j 보다 작다면

         4.3.1 배열의 i번째 요소와 j번째 요소를 교체한다.

 5. pivot과 배열의 i번째 요소를 교체한다.

 6. 배열의 pivot보다 앞부분(0번째 원소부터 i-1번째 요소까지의 배열)을 퀵소트로 재귀 호출

 7. 배열의 pivot보다 뒷부분(i+1번째 원소부터 끝까지의 배열)을 퀵소트로 재귀 호출

 

 

퀵 소트의 수행 속도 분석

T(n):수행 속도

4,6,7이 전체 수행 속도에 큰 영향을 미치는 부분들이다.

T'(n):4를 수행하는 속도라고 하면

T'(n) 은 최악의 경우 (n-1)번 비교, (n-1)/2번 교환

즉, T'(n) = 3*(n-1)/2

T(n)는 pivot이 가장 효율적으로 계속 선택된다면

T(n) = T'(n) + 2*T'(1/2) + 2^2T'(1/2^2) + 2^3T'(1/2^3) + ... + 2^h(1/2^h)  단,1/2^h = n

        = 3*(n-1)/2 + 2*(3*(n-1)/2)/2 + 2^2*(3*(n-1)/2)/2^2 +...+2^h*(3*(n-1)/2)/2^h 

        = (h+1)*(3*(n-1)/2)

1/2^h = n이므로 h = logn

즉, T(n) = (logn+1)*(3*(n-1)/2)

     T(n) = w(nlogn)

T(n)는 pivot이 가장 비효율적으로 계속 선택된다면

T(n) = T'(n)+T'(n-1)+T'(n-2) +...T'(1)이 될 것이다.

즉, T(n) = 3*(n-1)/2 + 3*(n-2)/2 + ... + 0

             = 3*n^2 -an (a는 계산하지 않겠음다.)

     T(n)= O(n^2)

 

 

퀵소트에 대한 본인의 생각

이는 퀵소트는 평균적으로 빠르지만 최악의 경우(어느정도 정렬된 자료 혹은 어느 정도 역순 정렬된 자료)에서 pivot을 적절히 선택하지 못한다면 다른 알고리즘에 비해 느린 알고리즘이 될 수 있다는 것을 시사한다.

 

전산에서 최악의 경우는 굉장히 중요한 의미를 시사한다.

이는 해당 행위를 하는데 해당 시간이 지나면 반드시 끝날 수 있다는 것을 보장함을 의미한다.

 

결론적으로 퀵소트는 평균적으로는 빠를지 모르지만 최악의 경우 빠르지 않기 때문에

전산적으로 보았을 때 빠르지 않다고 얘기하는 것이 더 적절하다고 생각한다.(물론 논쟁의 소지는 많다.)

 

많은 이들이 여전히 어떠한 값을 pivot으로 하는 것이 가장 효율적인 퀵소트가 되는가에 대한 연구는 계속되고 있다.

사이트 내 다시 정리한 글

퀵정렬 알고리즘 

퀵정렬 알고리즘 구현 및 C언어 소스