8. Quick sort

1. Quick sort

 

quick sort는 다음과 같다.

1) 배열을 shuffle한다.

2) 배열의 첫번째 요소를 기준점 pivot 으로 삼고, 두번째 요소, 마지막요소를 가리키는 두개의 포인터를 둔다.

3) 좌측의 포인터를 i, 우측의 포인터를 j라고 하면, pivot보다 커질 때까지 i를 우측으로 이동시키고, pivot 보다 작아질 때까지 j를 이동시킨다. 더 이상 i, j가 이동하지 못하면, a[i]와 a[j]를 교환한다. 그러면 다시 i가 가리키는 것은 pivot보다 작아지고, j가 가리키는 것은 pivot보다 커지므로 이동가능하게 된다. 이렇게 이동하다가 멈추면서 i가 j보다 크거나 같아지는 순간, pivot이 가리키는 값과 a[j]를 교환한다. 이때 a[j]의 값은 pivot의 값보다 항상 같거나 작게 된다.

따라서, 교환후에 a[j]를 기준으로 왼쪽은 a[j] 보다 같거나 작은것만 남게 되고, 오른쪽은 크거나 같은것만 남게 된다. 따라서, a[j]의 위치는 확정된다.

4) 다시 j를 기준으로 왼쪽배열에 대해서 위의 과정을 수행하고, 오른쪽 배열에 대해서 위의 과정을 수행한다.

수행할 때마다 하나의 요소의 위치가 확정된다.

 

quick sort의 worst case는 이미 정렬된것을 다시 정렬할 때 발생하고, 맨 끝요소의 위치가 확정됨을 반복하므로 결과적으로 배열을 절반으로 나누어 문제를 해결하는 divide-and-conquer의 이점을 활용하지 못한다. 이 때, 실행시간은 ~1/2N^2이다. 따라서, shuffle을 하게 되는데, shuffle을 하게 될 경우에 배열의 값들이 균등하게 분배되므로 이러한 일이 나올 확률은 사실상 불가능하다. 따라서 성능은 ~NlogN로 보장된다.

수학적으로 수행시간을 계산하면, 서로 다른 요소 N개를 가진 배열에 대해서  약 1.39NlogN성능을 갖는다.

이것은 mergesort에 비해 약 39%정도 나은 성능이다.

또한, mergesort와 다르게 배열복사를 위한 추가적인 공간을 필요로하지 않는(in-place) 알고리즘이다.

하지만, quicksort는 stable하지 않다. 

 

이러한 quicksort의 성능을 향상시킬 수 있는 방법 중 하나는, mergesort의 성능향상과 특정한 길이이하의 배열에 대해서는 insertion sort를 사용하는 것이다. 또한, pivot을 랜덤한 3개의 숫자중에 중간값을 선택함으로서, 배열의 좌우분할이 조금 더 균형있게 이루어지도록 하는것이다.

 

2. Selection

selection이란 N개의 item이 주어졌을 때, i번째로 큰/작은 item을 찾는 문제이다.

이것은 quick sort의 방식과 유사하게 하나의 위치를 확정시킨 후, 좌우배열 중 정렬이 완료되었을 때 존재해야하는 찾고하자하는 item의 위치방향으로 탐색을 다시 함으로서 해당 item을 찾아간다.

즉, quick sort와는 다르게 좌우배열중 한쪽 방향으로만 quick-sort를 반복하는 것이다.

이론상으로 이러한 quick select는 평균적으로 linear time에 해결될 수 있다. worst-case는 여전히 1/2N^2이다. 

worst-case에 대해서 linear time이 나오는 실용적으로 쓸만한 알고리즘을 찾는것은 여전히 open-problem이다.

 

3. Duplicate keys

많은 문제에서 실제로 정렬을 위한 key값은 서로 distinct한 값이 아닌 중복된 값인 경우가 많다.

이론상 너무 많은 값이 중복되어 있다면 그것이 좋은 모델이라고 볼수는 없지만, 실제로는 중복된값이 리스트로 들어가있는 경우가 많기 때문에 이것에 대해 논의하는 것은 유용하다.

중복된 값이 많은 배열에 대해서 quick-sort를 했을 경우, 실제적으로 quadratic time이 걸림이 밝혀졌다.

이러한 문제를 해결하기 위해서는 가능하면 파티셔닝하는 item을 모두 모아두는 것이 좋다.

Dijkstra의 3-way partitioning을 이용하면 partitioning item이 모두 한곳에 모이게 되어, 한 곳에 모인 값의 뭉텅이를 기준으로 좌우배열을 나누어 다시 sort를 수행한다.

이 방식은 수학적으로 계산했을 때, 모든 key가 distinct할 때, ~NlogN의 실행시간을 갖는다. 특히, key값이 될수있는 값들이 constant의 갯수로 이미 정해져있다면, 정렬은 linear time을 갖는다는 특징을 갖는다.

 

4. System sort

Java와 같은 언어는 Arrays.sort()라는 System sort를 제공한다. 각 언어나 프레임워크는 이러한 시스템 정렬 방식을 제공하고, 그것의 구현은 시스템마다 각각다르다. 또한, 모든 데이터, 모든 상황에 대해서 Optimal한 시스템 정렬은 존재하지 않는다. 우리는 특정한 상황에서 정렬의 성능을 향상시키기 위해서 시스템 정렬을 사용하는 것이 아닌 다른 방식의 정렬을 사용함으로서 성능을 향상시킬 수 있다. 

하지만, 여전히 시스템 정렬은 충분히 좋다. Java의 경우 객체에 대해서는 Merge sort를, Primitive type에 대해서는 Quick sort를 제공한다. 그 이유는, 객체를 사용한다는 것은 곧, 기억공간에 대해 크게 신경쓰지 않는다는 뜻이고,  추가배열을 사용하는 것을 용인한다고 생각하기 때문이다. 또한, 객체는 어러가지 데이터를 가지기 때문에 stability를 확보하는 것이 좋다. 그에 반해서 primitive type을 사용하는 프로그래밍에서는 성능과 자원이 더 중요한 것으로 생각되므로 quick sort를 사용한다.

 

출처 : Coursera. Princeton Algorithm part1 lecture