퀵 정렬 : 기준값(pivot)을 설정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 평균 시간복잡도는 O(N)이지만 기준값이 어떻게 설정되느냐에 따라 최악의 경우 O(N^2)이 된다.
핵심은 pivot을 중심으로 두 개의 집합으로 나누면서 정렬하는 것이다.
1 ) pivot을 제외한 나머지에서 가장 왼쪽에 있는 값을 start, 가장 오른쪽에 있는 값을 end라고 설정한다.
2 ) 여기서 공식은 start의 값이 pivot의 값보다 작을 경우 start를 오른쪽으로 한칸 옮긴다.
3 ) end의 값이 pivot보다 큰 경우 end를 왼쪽으로 한칸 옮긴다.
4 ) 만약 start의 값이 pivot보다 크고 end의 값이 pivot보다 작다면 두 값을 swap하고 start와 end를 각각 오른쪽 왼쪽으로 한 칸씩 옮긴다.
5 ) start와 end가 만날 때 까지 위의 로직을 반복한다.
6 ) start와 end가 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot의 값을 삽입한다.
7 ) 이후 분리된 집합에서 각각 pivot을 설정해 분리 집합이 1개 이하가 될 때까지 반복한다.
