퀵 정렬(Quick Sort)과 최악의 경우(O(N^2))를 방지하기 위한 방법들

이 글에서는 퀵 정렬에 대한 상세한 설명은 하지 않는다. 퀵 정렬은 평균 O(NlogN)의 시간 복잡도를 가지지만, 최악의 경우 O(N^2)의 복잡도를 갖는다.

그 이유를 모르는 사람에게는 이 글을 추천하지 않으며, 이 글을 읽을 시간에 자료구조 책을 보기를 권하겠다. 이 글에서는 내가 여러 알고리즘 서적들과, 블로그 등을 보면서 만나본 여러 가지 최악의 경우 방지 방법을 다루어보고, 이를 비교해보고자 한다. 1.

Quick Sort 첫 번째로, 그럼 퀵 정렬의 평균적인 경우와 최악의 경우의 시간 차이가 얼마나 발생하게 되는지를 먼저 알아보자. 다음 소스코드는 pivot을 배열의 첫 번째 원소로 하는 단순한 퀵 정렬의 소스코드이다. void firstPivotQicksort(int *arr, int begin, int end) { if (end <= begin) return; int pivot = begin, left = begin, right = end + 1; while (lef...