[CS] 퀵 정렬(Quick Sorting)

찰스 앤서니 리처드 호어라는 사람이 만든 정렬 알고리즘이다.

분할 정복(Divide and Conquer) 방식을 기반으로 하며

최악의 경우 O(N^2), 평균적인 경우 O(n log n)의 시간 복잡도를 가진다.

요소들이 균일하게 섞여있는 경우 가장 빠르며, 내림차순으로 정렬되어 있을 때에 가장 느리다.

이름에서도 알 수 있듯, 가장 빠른 정렬 알고리즘들 중 하나에 속한다.

 

분할 정복방식이란?

분할 정복 방식이란 말 그대로 어떤 커다란 문제를 여러 개의 작은 문제로 분할 한 뒤, 각각을 해결하고,

해결된 각 부분을 합하여 전체의 문제를 정복하는 문제 해결 방식이다.

퀵 정렬도 이러한 방식을 기초로 하고 있다.

 

퀵 정렬 알고리즘의 수행 과정

1.배열의 첫번째 요소를 피벗(Pivot)으로 정한다.

   여기서 피벗이란 배열의 기준 요소로,해당 요소의 앞에는 그보다 작은 값이,해당 요소의 뒤에는 그보다 큰 값이 위치해야 한다.

2.피벗 앞의 요소를 i라고 하고, 배열의 마지막 요소를 j라고 하자.

  i는 pivot보다 큰 값을 찾을 때까지 배열 뒤쪽으로 이동하고,

  j는 반대로 pivot보다 작은 값을 찾을 때까지 배열 앞쪽으로 이동한다. 

3.둘 다 해당하는 값을 찾은 상태인 경우 i와 j을 교환한다.

4.이 과정을 i와 j가 엇갈릴 때까지 반복한다.

5.i와 j가 엇갈렸으면, j와 pivot을 교환한다.

6.교환된 배열은 pivot 앞쪽엔 작은 값이, 뒤쪽에는 큰 값들만 위치하게 된다.

7.하지만 피벗 외의 요소들은 정렬되어 있지는 않은 상태이므로, 분할 정복 방식으로 해당 블록들을 다시 퀵 정렬한다.

8.피벗보다 작은 요소들의 퀵 정렬 + 피벗 + 피벗보다 큰 요소들의 퀵 정렬이 완료되면,

  최종적으로 오름차순으로 정렬된 배열이 결과로 나오게 된다.