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

Quick Sort란?

• 분할 정복 방법을 통해 주어진 배열을 정렬
• 불안정 정렬
• 배열을 비균등하게 분할 / 정렬된 배열일수록 수행시간이 오래 걸림
• 매우 빠른 속도

분할 정복 방법이란?
[문제를 작은 2개의 문제로 나눠 각각 해결한 후 결과를 모아서 원래의 문제를 해결하는 전략

 

Quick Sort 과정

1. 배열에서 하나의 원소를 고른다. 이 원소를 피벗(pivot)이라 한다.
2. 피벗의 기준을 2개로 나눈다.( 피벗보다 작은 건 앞으로, 큰 건 뒤로) => 이 과정을 분할이라 하며 분할 후 피벗은 고정한다.
3. 분할된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.

• 정복 -> 분할 -> 결합 순으로 이루어진다.

시간 복잡도

• 최선의 경우 => n -> n/2 -> n/4 ->... -> 1 = O(nlog₂n)
• 최악의 경우(배열이 오름,내림차순으로 정렬되어 있는 경우) => O(n^2)

최악	평균	최선
O(n^2)	O(nlog₂n)	O(nlog₂n)