퀵 정렬 (Quick Sort)

퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 방법을 이용하여 정렬을 수행하는 알고리즘 중 하나입니다.

 

평균적인 경우 O(nlogn)의 시간 복잡도를 가지며, 최악의 경우 O(n^2)의 시간 복잡도를 가집니다.

 

퀵 정렬의 아이디어는 하나의 배열을 기준(pivot) 값을 기준으로 두 개의 하위 배열로 분할하고, 이 하위 배열들을 각각 다시 퀵 정렬을 수행하여 정렬하는 것입니다.

 

이때 pivot 값을 기준으로 작은 값들은 pivot의 왼쪽에, 큰 값들은 pivot의 오른쪽에 위치하게 됩니다.

 

퀵 정렬의 핵심은 pivot 값을 적절하게 선택하는 것입니다.

 

일반적으로 배열의 가운데 값을 pivot으로 선택하거나, 무작위로 선택하는 방법이 사용됩니다.

 

또한 pivot 값을 선택한 후, pivot 값보다 작은 값을 pivot의 왼쪽으로, 큰 값을 pivot의 오른쪽으로 이동시킵니다.

 

이를 위해 배열의 끝 부분을 포인터(right)로, 시작 부분을 포인터(left)로 지정하고, left와 right가 만날 때까지 반복적으로 pivot 값보다 큰 값을 찾아 left와 right의 위치를 교환합니다.

 

이렇게 pivot 값보다 작은 값과 큰 값으로 분할한 하위 배열들을 각각 다시 퀵 정렬을 수행하며 정렬합니다.

 

이 과정은 하위 배열의 크기가 1이 될 때까지 반복됩니다.

 

아래는 퀵 정렬의 동작 원리를 그림으로 나타낸 것입니다.

 

출처: https://en.wikipedia.org/wiki/Quicksort#Animation

 

퀵 정렬의 장점은 평균적으로 빠른 속도와 간단한 구현 방법입니다.

 

하지만 pivot 값에 따라서 성능이 크게 달라질 수 있으며, 최악의 경우 시간 복잡도가 O(n^2)로 나타날 수 있습니다.

 

또한, 퀵 정렬은 원래 배열을 변경하므로 추가적인 메모리를 사용하지 않습니다.