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

퀵 정렬

퀵소트는 divide and conquer 방법을 통해 정렬한다.

리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피봇이라고 한다.

피봇 앞에는 피봇보다 값이 작은 모든 원소들이 오고, 피봇 뒤에는 피봇보다 값이 큰 모든 원소들이 오도록 피봇을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피봇은 더 이상 움직이지 않는다.

분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

[ 위키백과 참조 ]

시간 복잡도

( T(n) 은 n의 리스트를 정렬하는데 걸리는 시간 )

평균적으로 O(nlog n) 의 시간복잡도를 갖는다.

최선의 경우 : O(nlog n) 

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

역순으로 정렬되어 있거나 정렬된 배열을 정렬하는 경우가 최악의 경우에 해당한다.

맨 앞의 데이터를 pivot으로 선택했다면 데이터가 분할되지 못하므로 한번의 비교연산이 n번 이루어진다.

이러한 문제를 해결하려면 pivot을 중간값을 기준으로 선택해야한다.