퀵소트

정렬 알고리즘 중 O(nlogn)의 시간 복잡도를 가진 정렬 기법

하지만 최악의 경우에는 O(n^2)까지 나타날 수 있다.

 

퀵소트는 분할정복(명확히 말하면 정복분할)을 이용한 정렬인데

피봇을 기준으로 계속해서 0, n-1으로 배열이 나눠지는 경우에는 n^2이 된다.

이런 경우는 이미 역정렬이나 정렬이 된 상태일 경우

 

이런 경우를 방지하기 위해서는 피봇을 맨처음이나 끝이아닌

중간값이나 중앙값으로 잡아주면 방지할 수 있다.