Quicksort 개선하기

■ 방법1 : 비재귀로 구현

quick_sort()함수로 20,000개 정도의 정수를 정렬하다보면 갑자기 이상한 문자가 나오면서 실행이 중지되는 현상이 생길 수 있다. 이는 내부 스택의 오버플로로 프로그램이 강제로 중지되기 때문이다.

한 번의 재귀 호출로 복귀 주소 2바이트, n 2바이트, a 2바이트해서 모두 6바이트의 스택이 사용된다. 20,000개 정도의 정수를 퀵 정렬하기 위해서는 정확히 분할이 이등분된다면 재귀의 깊이가 15(log220000)이면 되므로 15*6=90바이트 밖에 스택이 쓰지 않는다. 하지만 최악의 경우(역순 배열이나 정렬된 배열의 경우)N만큼 재귀가 깊어지므로 20000*6=120000바이트 약 120KB 가량이 소모되어 스택은 넘치게 된다. 이런 문제를 해결할 수 있는 방안은 재귀 호출을 없애고 직접 스택을 만들어 쓰는 것이다.

이렇게 직접 스택을 만들어쓰게되면 함수 호출에 의한 오버헤드 현상으로 속도가 시원 스럽게 오르지 않는다. 정렬된 배열과 역순 배열의 경우 그렇지 않은 경우에 비해 무려 40배 가량이나 느리다.

■ 방법2 : 난수 분할

정렬된 배열과 역순 배열일 때 퀵 정렬의 속도가 현저히 느려지는 것은 축값으로서 가장 오른쪽의 값을 택하기 때문에 결과적으로 가장 큰 값이나 가장 작은 값이 축값이 되기때문이다.

이 문제의 해결 방법은 축값을 잘 선택하는 것이다. 하지만 입력되는 자료가 임의적인 것이므로 일관적인 방법으로 축값을 잘 선택하는 방법은 없다 한 가지 대안으로 제시되는 것은 축값을 난수(random)으로 선택하는 것이다.

■ 방법3 : 삽입정렬

큇 정렬이 더 이상 빨라질수 있는가? 퀵정렬은 구간을 쪼개면서 정렬을 해 나간다. 큰 구간을 쪼개나가는 것은 퀵 정렬로 하고 작은 구간에 대해서는 더 성능좋은 알고리즘을 사용하면 된다.

삽입 정렬은 구현이 간단하면서도 작은 크기의 배열에서는 매우 효율이 좋다. 또한 삽입 정렬은 추가적인 메모리를 필요치 않는다. 작은 구간에 대한 삽입 정렬을 사용 하는 것은 퀵 정렬의 재귀의 깊이를 상당히 줄여줌으로써 메모리의 부족에 대한 문제를 어느 정도 해결하게 해준다.

■ 방법4 : 세 값의 중위

난수로 분할값을 정하는 방법 외에도 세 값의 중위(Three of midian)를 이용하여 퀵 정렬을 개선시키는 방법도 있다. 세 값이라는 것은 가장 왼쪽의 값a[l]과 가장 오른쪽의 값 a[r]과 중간의 값 a[(r+1)/2)]을 의미한다.

이 세 값을 정렬하여 가장 작은 값을 왼쪽에 중간값을 중간에 가장 큰 값을 가장 오른쪽으로 옮긴다. 다음으로 중간값과 가장 오른쪽 앞의 값(a[r-1])을 바꾼다. 그런 다음에 a[r-1]로 (원래는 중간값이었다) 분할을 실시하는데 가장 왼쪽값은 이 a[r-1]보다 작은 것이 확실하고(정렬했으므로), 가장 오른쪽값은 a[r-1]보다 크다는 것이 확실하므로 구간에서 제외하고 a[l+1]부터 a[r-2]로 범위를 줄인다.

이렇게 범위에서 2개를 줄이는 것만으로도 재귀의 깊이를 상당히 줄일 수 있으며 분할도 거의 중앙에서 이루어질 가능성이 많다.(적어도 세 개중에서는 중앙이므로). 특히 정렬된 배열이나 역순의 배열은 분할을 정 중앙에서 할 수 있으므로 이 방법을 쓰면 가장 속도가 빨라진다.

출처 : http://algori.egloos.com/v/333555
median of three(세 값의 중위) 소스코드 : https://github.com/JaeguKim/Algorithm/blob/master/Median_Of_%20Three_Quicksort/median_of_three_qsort.cpp