[Algorithm] 퀵 정렬(Quick Sort)

퀵 정렬이란?

퀵 정렬이란 분할 정복 알고리즘의 하나로, 매우 빠른 수행 속도를 가지고 있습니다.

어떤 방식으로 실행되는지 예시를 살펴보겠습니다.

1 10 6 3 9 5 8 2 4 7

이렇게 10개의 원소가 존재한다고 가정하겠습니다.
우리는 이 중에서 피벗(pivot)으로 사용할 원소를 하나 선택해야 합니다.
피벗은 정렬되지 않은 원소 중 제일 왼쪽에 있는 원소로 선택합니다.
그렇게 피벗을 선택한 이후, 피벗보다 작은 숫자는 모두 왼쪽으로, 피벗보다 큰 숫자는 모두 오른쪽으로 이동시켜 주면 됩니다.

그렇게 하기 위해서는 배열의 왼쪽부터 탐색하며 피벗보다 큰 숫자를 찾아줍니다. 이후 배열의 오른쪽부터 탐색하며 피벗보다 작은 숫자를 찾아줍니다. 두 숫자를 바꿔줍니다.
계속 반복하다 보면 찾은 두 숫자의 인덱스가 교차하는 순간이 오게 됩니다. 그렇게 된다면 피벗보다 작은 숫자와 피벗의 위치를 교환해줍니다.

세부 예시는 다음과 같습니다. (이미 정렬된 숫자는 BOLD로, 피벗은 블록으로 표시)

1 10 6 3 9 5 8 2 4 7
1 10 6 3 9 5 8 2 4 7
1 7 6 3 9 5 8 2 4 10
1 7 6 3 4 5 8 2 9 10
1 7 6 3 4 5 2 8 9 10
1 2 6 3 4 5 7 8 9 10
1 2 6 3 4 5 7 8 9 10
1 2 6 3 4 5 7 8 9 10
1 2 6 3 4 5 7 8 9 10
1 2 5 3 4 6 7 8 9 10
1 2 5 3 4 6 7 8 9 10
1 2 4 3 5 6 7 8 9 10
1 2 4 3 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

이렇게 정렬이 완성되게 됩니다.

시간 복잡도

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