Quick Sort

divide & conquer algorithm

 

pivot이라고 불리는 임의의 값을 기준으로 분할 정복

 

쿽 정렬의 성능은 어떠한 pivot 값을 선택하느냐에 영향을 많이 받는다.

 

Best Case에서는 pivot 값을 기준으로 동일한 개수의 작은 값들과 큰 값들이 분할되어 merge sort와 마찬가지로 O(nlogn)의 시간 복잡도를 가지게 된다.

 

하지만 pivot 값을 기준으로 분할했을 때 값들이 한 편으로 크게 치우치게 되면 성능이 저하된다. Worst Case의 경우 한 편으로만 모든 값이 몰리게 되어 O(n^2)의 시간 복잡도를 가진다.

 

따라서 상용화를 할 때에는 중앙값(median)에 가까운 pivot 값을 선택하는 것이 좋다.

배열의 처음, 중앙, 마지막에 들어있는  값들 중에 크기가 중간인 값을 사용하는 방법이 많이 사용된다.

 

 

 

Python Code