퀵소트(Quick Sort)

간단하게 요약하자면

피폿을 기준으로 왼쪽에는 작은수를 오른쪽에는 큰 수를 배치하면서 정렬하는 알고리즘

 

 

"왼-작은수/오-큰수를 배치하려면 어떻게 해야할까요?"

 

 

방법

1. 피봇의 왼쪽 끝에서는 피봇보다 큰수를, 오른쪽 끝에서는 찾아서 스왑해주면 됩니다.

2. 왼쪽/오른쪽 찾는 위치가 반대가 될 경우 = 왼-작은수/오-큰수 배치가 이미 되었다는 의미

3. 피봇과 오른쪽 찾는 위치와 스왑해 줍니다.

4. 피봇은 알맞은 위치를 찾았지만 왼쪽/오른쪽 구역은 정렬이 되지 않았습니다. 해당 구역들을 1-3번 방법으로 반복해줍니다.

 

 

 

 

''일반 정렬 방법들보다 얼마나 빠를까요?'

 

 

장점

보통 O(n^2) 시간복잡도를 가지는 선택/삽입 정렬에 비해 평균적으로 빠릅니다.

O(nlog2n) 의 시간복잡도를 가지고 있습니다.

 

우선 정렬 범위가 반씩 줄어들기 때문에 log2n 정도 걸립니다.

그 안에서<N 반복하며 스왑해주기 때문에 O(nlog2n)정도의 시간이 걸립니다.

 

 

 

단점

이미 역/정렬되어있을 경우 (= 최악의 경우) O(n^2)의 시간이 걸린다는 단점이 있습니다. 

절반씩 정렬 범위를 줄여야 하는데 정렬이 되어 있다면 피봇은 항상 맨 끝에 위치하게 되고 피봇을 중심으로 구간이 절반씩 나누어 지지 않습니다. 결국 n * (n-1) .. 반복하게 되어 O(n^2)이 됩니다.

 

 

 

활용

이러한 단점이 있지만 STL의 Algorithm - sort 함수가 퀵소트 방식을 사용한다고 합니다.