[Algorithm] Quick Sort(퀵 정렬)

[Algorithm] Quick Sort(퀵 정렬)

1. 정의

• 피벗(기준)을 하나를 정해서 피벗보다 큰 수는 오른쪽 작은수는 왼쪽으로 옮겨가며 정렬하는 기법
• 불안정 정렬
• 시간 복잡도
  • 평균 : $O(nlogn)$
  • 최악 : $O(n^2)$

2. 동작 과정

1. 피벗을 하나 정한다.
2. 양 끝에 포인터를 각각 두고 포인터를 움직인다.
   2 - 1. 왼쪽 포인터는 피벗 보다 큰 값이 나올때까지 오른쪽으로 움직인다.
   2 - 2. 오른쪽 포인터는 피벗 보다 작은 값이 나올때까지 왼쪽으로 움직인다.
   2 - 3. 값을 찾으면 서로 교환한다.
   2 - 4. (2 - 1) ~ (2 - 3)을 반복한다.
3. 포인터가 서로 교차하면 2개의 구간이 생기는데, 각각의 구간 별로 1번부터 반복한다.

3. 장단점

• 장점
  • 병합 정렬과는 달리 추가적인 공간이 필요하지 않음
• 단점
  • 피벗에 따라 속도가 달라질 수 있음
  • 피벗을 임의로 잡기 때문에 LinkedList에서는 효율이 나쁨

4. 코드

public void quickSort(int[] array, int left, int right) {

   int part2Start = partition(arry, left, right);
   int part1End = part2Start - 1;

   if (left < part1End) {
       quickSort(array, left, part1End);
   }

   if (part2Start < right) {
       quickSort(array, part2Start, right);
   }
}

//두 개의 구간중 오른쪽 구간의 첫번째 인덱스를 반환한다.
public static int partition(int[] array, int left, int right) {
   int pivot = array[(left + right) / 2];//피벗은 중간지점으로 정함

   while (left <= right) {
       while (array[left] < pivot) { //왼쪽에서 피벗보다 큰 값 찾기
          left++;
       }

      while (array[right] > pivot) { //오른쪽에서 피벗보다 작은 값 찾기
         right--;
      }

      if (left <= right) {
         swap(array, left++, right-- );
      }
   }

   return left;
}

private static void swap(int[] array, int left, int right) {
   int tmp = array[left];
   array[left] = array[right];
   array[right] = tmp;
}

---

※ 참고

• [알고리즘] 퀵 정렬 알고리즘 (Quick Sort)
• tech-interview-for-developer/Algorithm/QuickSort
• [자료구조 알고리즘] 퀵정렬(Quicksort)에 대해 알아보고 자바로 구현하기