개요
퀵 소트란 나열된 수에서 적당한 값(축)을 기준으로 이보다 작거나 같은 값을 왼쪽에, 크거나 같은 값을 오른쪽에 오도록 재배열하는 것이다. 이렇게 만들어진 왼쪽, 오른쪽 부분수열에 대해 같은 과정을 반복하면 퀵정렬이 완성된다. 합병 정렬은 부분수열이 항상 같은 크기로 선정되지만, 퀵 소트는 그렇지 않다.
알고리즘
- 피벗을 적당히 구한다.
- 피벗의 오른쪽에는 피벗보다 큰 값을, 왼쪽에는 피벗과 같거나 작은 값을 넣는다.
- 오른쪽 원쪽 부분수열의 길이가 1 또는 0 이 될따까지 위 작업을 반복한다.
이떄 피벗의 오른쪽에 피벗보다 큰 값을 넣고 왼쪽에는 피벗과 작은 값을 넣는 알고리즘은 다음과 같다.
- 오른쪽으로 검사하면서 축보다 크거나 같은 값이 있는 위치(i)를 찾는다.
- 왼쪽으로 검사하면서 축보다 작거나 같은 값이 있는 위치(j)를 찾는다.
- i >= j 이면 찾기를 종료하고 왼쪽 끝 항과 j항을 교환한다. 교환후 다음 피벗을 구하려 간다.
- i항과 j항을 교환한다. 교환후 2로 다시 돌아간다.
시간 복잡도
최악의 경우
피벗이 극단적인 값을 대표하는 경우 깊이 n 에 비교 n 모두 곱하여 n^2 이다.
평균의 경우
깊이 logN 비교 N 곱하여 NlogN 이다. 이때 퀵 소트는 평균적인 경우 합병 정렬보다도 빠르게 정렬한다고 알려져 있다.
최적화
- 축 선택을 중앙값으로 한다.
- 부분수열의 길이가 특정 길이보다 짧아지면, 삽입법을 이용한다.
- 재귀 호출을 제거하고 반복 형태로 프로그램을 변경한다.