퀵정렬 알고리즘

최악 시간 복잡도는 O(n2)

최선 시간 복잡도는 O(n log n)

평균 시간 복잡도는 O(n log n)

 

퀵 정렬은 분할정복 방법을 통해 리스트를 정렬한다.

 

1. 리스트 가운데 하나의 원소를 고른다 고른 원소를 피벗이라고 한다.

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

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