퀵 정렬

 

퀵 정렬 개념

 

n개의 정렬할 원소가 있다고 할때

 

피봇을 하나 정하여 n-1개의 원소를 피봇보다 작은 원소는 왼쪽으로 피봇보다 큰 원소는 오른쪽으로 옮긴다.

 

그러면 피봇 원소의 위치는 정렬이 모두 되었을때의 피봇 원소의 위치와 같아진다.

 

 

 

피봇의 원소를 기준으로 왼쪽 원소들과 오른쪽 원소들을 완전히 나누었으므로 

 

왼쪽 원소들로만 재귀함수를 이용하여 퀵정렬을 하고

 

오른쪽 원소들로만 재귀 함수를 이용하여 퀵정렬을 한다.

 

 

 

만약 왼쪽이나 오른쪽의 원소의 수가 1보다 작거나 같다면 기저조건이므로 해당 퀵정렬을 종료한다.

 

 

 

 

퀵 정렬의 시간 복잡도

 

n개의 원소들 중에서 피봇을 기준으로 왼쪽과 오른쪽으로 n-1개의 원소들을 분류하는 시간복잡도는 O(n)이다.

 

대략적인 시간 복잡도를 계산하기 위하여 만약 피봇이 원소를 정확하게 절반으로 나눈다고 가정하면

 

T(n) = 2T(n/2) + O(n) 이므로 T(n) = O(nlogn)이 된다.

 

 

 

만약 피봇이 원소들을 분류해주지 못하는 최악에 상황에서는

 

(ex : 123456789 에서 피봇을 맨 앞의 원소로 잡는 경우)

 

퀵정렬의 시간 복잡도는 T(n) = O(n^2)이 된다.