[알고리즘] 정렬 - 퀵 정렬(quick sort)

🟡 퀵 정렬(quick sort)

- pivot 값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 방식

- 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미침

- 평균적인 시간 복잡도: O(n * logn)

- 최악일 경우 시간 복잡도: O(n^2)

- 분할 정복을 사용

 

 

🟡 퀵 정렬 과정

pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 핵심

① 데이터를 분할하는 pivot을 설정한다.

② pivot을 기준으로 다음 a~e 과정을 거쳐 데이터를 2개의 집합으로 분리한다.

②-ⓐ start는 왼쪽에서 오른쪽으로 탐색하다가 pivot보다 큰 데이터를 찾으면 멈춘다.

②-ⓑ end는 오른쪽에서 왼쪽으로 탐색하다가 pivot보다 작은 데이터를 찾으면 멈춘다.

②-ⓒ start와 end가 가리키는 두 데이터를 swap한다. start는 오른쪽, end는 왼쪽으로 1칸씩 이동한다.

②-ⓓ start와 end가 만날 때까지 ②-ⓐ~②-ⓒ를 반복한다.

②-ⓔ start와 end가 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입한다.

③ 분리 집합에서 각각 다시 pivot을 선정한다.

④ 분리 집합이 1개 이하가 될 때까지 과정 ①~③을 반복한다.