퀵 정렬 (Quick sort)

퀵 정렬 이란?

기준값(pivot)을 잡고 데이터를 2개의 집합으로 쪼개어가며 정렬하는 방법이다.

시간복잡도는 평균적으로 O(NlogN)이며 최악의 경우 O(N^2)가 된다.

퀵 정렬 과정

1. pivot 설정(사용자 마음이며 위 그림의 경우 맨 오르쪽을 pivot으로 잡음)
2. pivot을 기준으로 다음 과정을 거쳐 2개의 집합으로 분할
   1. start 포인터가 가르키는 데이터가 pivot보다 작을 경우 start 포인터 오른쪽으로 이동, 아닌 경우 멈춤
   2. end 포인터가 가르키는 데이터가 pivot 보다 클 경우 end 포인터 왼쪽으로 이동, 아닌 경우 멈춤
   3. start 포인터와 end 포인터 모두 멈춘 경우 두 데이터 swap
   4. start 포인터와 end 포인터가 만날 때 까지 위 과정 반복
   5. start 포인터와 end 포인터가 만난 지점의 데이터와 pivot 데이터를 비교하여 pivot 데이터를 적절한 위치에 삽입 (= 2개의 집합으로 분리됨)
3. 분리 집합에서 각각 다시 pivot 설정
4. 각각의 분리 집합의 원소가 1개 이하가 될 때 까지 위 과정 반복

 

재귀 함수의 형태로 구현해 볼 것