[ 알고리즘 / 정렬 ] 퀵 정렬 (Quick Sort)

 퀵 정렬 (Quick Sort)이란?

- 분할 정복 알고리즘 중 하나로 pivot을 기준으로 양쪽으로 정렬하는 알고리즘이다.

- 병합 정렬과는 다르게 배열을 비균등하게 분할한다.

 

 Process 

① 배열에서 하나의 원소(Pivot)을 고른다.

② (분할) Pivot 앞에는 Pivot보다 작은 원소들이 오고, Pivot 뒤에는 Pivot보다 큰 원소들이 오도록 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.

③ 분할된 두 배열에 대해 재귀적으로 이 과정을 반복한다.

 Code 

 

 

 시간복잡도 

 최선의 경우 : O(nlog₂n) 

* 비교 횟수 =>  log₂n

 

레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k) 했을 때, n=2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다.

 

* 각 순환 호출 단계의 비교 연산 => n

각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.

 

따라서, 최선의 시간복잡도는 순환 호출의 깊이 X 각 순환 호출 단계의 비교 연산 = nlog₂n 가 된다.

이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.

 최악의 경우 : O(n^2) 

- 이미 내림차순 or 오름차순으로 정렬

 

* 비교 횟수 =>  n

레코드의 개수 n이 2의 거듭제곱이라고 가정(n=2^k)했을 때, 순환 호출의 깊이는 n 임을 알 수 있다.

 

* 각 순환 호출 단계의 비교 연산 => n

각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다.

 

따라서, 최악의 시간복잡도는 순환 호출의 깊이 X 각 순환 호출 단계의 비교 연산 = n^2 다.

이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.

 공간복잡도 

주어진 배열 안에서 교환하기 때문에, O(n)이다.

 장점 

- 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 Pivot은 추후 연산에서 제외되기 때문에 달느 정렬 알고리즘에 비해 가장 빠르다.

- 정렬하고자 하는 배열 안에서 교환하기 때문에, 다른 메모리 공간을 필요로 하지 않는다 => 제자리 정렬(in-place sorting)

 단점 

- 불안정 정렬이다.

- 정렬된 배열에 대해서는 오히려 수행시간이 더 오래 걸린다.

 

 정렬 알고리즘 시간 복잡도 비교