Quick Sort (퀵 정렬)

퀵정렬은 임의의 한 요소(pivot이라 칭함)를 정한 뒤, pivot의 왼쪽에는 pivot보다 작은 것들만, 오른쪽에는 pivot보다 큰 것들만 오게 만드는 Divide & Conquer 알고리즘이다.

Quick Sort 내부에서 divide, 즉 partition하는 과정에 있어 크게 두 가지 접근법이 있다.

1) Hoare's Partition Scheme

2) Lomuto's Partition Scheme

먼저 Hoare's Partition Scheme에 대해 살펴보자.

전체 과정을 정리해 보면 다음과 같다. 특히 Partition 과정을 집중적으로 보도록 하자,

1. 배열의 첫 인덱스를 start로, 길이를 end로 하여 quickSort()를 호출한다. end는 배열의 마지막 index가 아닌 배열의 길이임에 주의하자.

2. quickSort() 내부에서 partition()을 수행하여 pivotIndex를 구한다.

   ㄴ < Partition > 

첫번째 요소를 pivot으로 저장한다.

맨 왼쪽 index를 i, 맨 오른쪽 index를 j에 할당한다.

i가 j보다 작은 동안 반복한다:

pivot보다 작은 값이 나올 때까지 j를 감소시킨다.

i < j 이면, j에 위치한 값을 i에 넣는다.

pivot보다 큰 값이 나올 때까지 i를 증가시킨다.

i < j 이면, i에 위치한 값을 j에 넣는다.

j에 pivot을 삽입하고, j를 리턴한다. (j가 곧 pivotIndex)

          

3. pivotIndex의 좌측과 우측 부분 배열에 대해 재귀적으로 quickSort()를 호출한다.

   (단, start와 end가 바로 옆에 붙어 있을 경우에는 quickSort에서 아무 것도 하지 않는다)

• j와 i를 왔다 갔다하면서 서로 할당하므로, 기존 배열에 데이터를 덮어 쓰더라도 결과적으로 손실이 없다.
• 주의) 가장 왼쪽 요소를 pivot으로 하고 저장한 다음 반복을 시작하므로, 반드시 오른쪽(j)부터 비교를 시작해야만 데이터를 잃지 않는다.
• partition: 어떤 원칙에 의해 pivot을 정하고, pivot의 왼쪽에는 pivot보다 작은 수만, 오른쪽에는 pivot보다 큰 수만 오도록 위치시킨다.
  (pivot 고르는 방법은 자유롭게 정해도 되지만, 여기서는 가장 왼쪽 요소로 한다.)
• partition을 수행한 후 왼쪽과 오른쪽 배열에 대해 각각 quickSort를 수행 => recursive; 즉 모든 요소가 pivot이 됨.
• partition의 마지막 부분에서 'j'에 pivot값을 넣는데, 해당 위치는 모든 정렬 과정을 마친 뒤의 최종 위치가 된다. 즉 해당 위치를 결정하고, 그 왼쪽과 오른쪽 요소들에 대해 다시 Quicksort를 진행...을 반복하는 방식이다.
• in-place(제자리 정렬): merge sort와 비교되는 quick sort의 장점. 메모리를 덜 필요로 한다.
• 평균적으로 O(nlogn): pivot을 어떻게 설정하느냐에 따라 달라질 수 있다.
• unstable(불안정적): 멀리 떨어진 위치로 요소를 이동시키게 되므로 unstable하게 될 가능성이 존재한다.

다음으로는 Lomuto's Partition Scheme을 보자. partition하는 방식이 완전히 다르며, main 메소드에서 quickSort를 call할 때 마지막 매개변수에 차이가 있다.