[JAVA] 퀵정렬 (Quick Sort)

퀵정렬 (Quick Sort)

---

퀵정렬 (Quick Sort)

• 분할정복 (divide and conquer) 알고리즘 중 하나
• 피벗(pivot)이라는 것을 이용해 정렬
  피벗 : 데이터 리스트에서 하나를 고르는 것
• 불안정 정렬 (unstable sort)
   - 같은 데이터끼리의 순서가 보장되지 않음
  ex) 5(A), 5(B), 3, 2, 1 => 1, 2, 3, 5(B), 5(A)
• nlog2(n) 알고리즘들 중 평균적으로 가장 빠름
• 제자리 정렬 (in-place sort)
   - 데이터 크기만큼의 저장공간을 제외하고 추가적인 공간이 필요하지 않음

퀵정렬 방법

1. 데이터들 중 하나를 골라 피벗으로 설정
2. 데이터 리스트의 앞과 뒤에서 탐색하며 피벗보다 작은 값들은 앞에 오고 피벗보다 큰 값들은 뒤로 가도록 분할
3. 분할된 리스트에 1, 2 과정을 반복
4. 1, 2 과정을 반복할 때마다 최소 하나 이상 정렬이 됨
    - 피벗값 기준으로 왼쪽은 작은값, 오른쪽은 큰 값이기 때문

성능

• 시간복잡도
  최악의 경우 : O(n^2)
  최선의 경우 : O(nlog2(n))
  평균의 경우 : O(nlog2(n))
  
  
• 피벗 데이터가 자신의 위치를 찾아가기 위해서는 데이터 개수 (n) 만큼의 비교연산이 필요
  
  
• 피벗값이 항상 리스트의 가운데에 있다고 가정할 때, 데이터들은 절반씩 나누어짐
  

  

  초기상태	1 덩어리	분할 0번
  17을 둘로 나누면	2 덩어리	분할 1번
  8을 둘로 나누면	4 덩어리	분할 2번

  위와 같은 과정을 거치게 되면 최종적으로 분할횟수 = log2(데이터 개수) 가 된다.
  
  
• 리스트가 이미 정렬되어 있고 피벗값이 항상 데이터들 중 가장 작은 값일 때, 데이터들은 n, n-1, n-2, ... 로 나누어짐
   - 피벗값이 리스트 내 데이터들 중 항상 작으므로 피벗과 이미 정렬된 데이터를 제외하고 모두 비교해야 하므로
  분할횟수 = 데이터 개수가 된다.
  
  
• 그러나, 퀵정렬의 경우 최악의 경우를 빅-오로 사용하지 않음
   - 중간에 가까운 피벗을 선택함으로써 최선의 경우에 가까운 성능을 평균적으로 보이기 때문

 

구현

• 기본 구현
  [QuickBasic.java]
  

  package Sort.Quick;
  
  public class QuickBasic {
      public static void sort(int[] arr) {
          quickSort(arr, 0, arr.length - 1);
      }
  
      private static void quickSort(int[] arr, int start, int end) {
          // end가 start보다 크다는 것은 더 나눌 데이터가 남아있다는 것이 됨
          if (start <= end) {
              // 피벗 대상이 될 인덱스 반환
              int pivotIndex = partition(arr, start, end);
  
              // 피벗 기준으로 왼쪽 데이터 분할
              quickSort(arr, start, pivotIndex - 1);
              // 피벗 기준으로 오른쪽 데이터 분할
              quickSort(arr, pivotIndex + 1, end);
          }
      }
  
      private static int partition(int[] arr, int start, int end) {
          // 배열의 처음, 중간, 끝의 데이터를 정렬해 크기가 중간인 데이터를 배열의 첫번째로 옮기는 과정
          medianOfThree(arr, start, end);
  
          // 피벗값을 제외하고 탐색해야 하므로 + 1
          int leftIndex = start + 1;
          int rightIndex = end;
          int pivotData = arr[start];
  
          // 탐색 인덱스들이 서로 지나치지 않았다면 반복
          // 지나쳤다면 해당 피벗을 이용한 탐색이 끝났으므로 반복문 종료
          while(leftIndex <= rightIndex) {
              // 피벗 데이터보다 큰 값이 나올때까지 탐색
              // leftIndex를 비교하는 부분이 앞으로 와야 함. 피벗값과 데이터가 같을 때 인덱스를 벗어날 수 있음. (ex. 4 4 1 2 2)
              while(leftIndex <= end && arr[leftIndex] <= pivotData) {
                  leftIndex++;
              }
  
              // 피벗 데이터보다 작은 값이 나올때까지 탐색
              // 피벗 데이터는 탐색에서 제외해야 함
              // rightIndex를 비교하는 부분이 앞으로 와야 함. 피벗값과 데이터가 같을 때 인덱스를 벗어날 수 있음.
              while(rightIndex >= start + 1 && arr[rightIndex] >= pivotData) {
                  rightIndex--;
              }
  
              // 서로의 인덱스가 지나치지 않았을 때 교환
              if (leftIndex <= rightIndex) {
                  swap(arr, leftIndex, rightIndex);
              }
          }
  
          // 피벗값과 rightIndex가 가리키는 값과 교환
          // rightIndex는 피벗값보다 작은 값을 탐색하는데, 서로 인덱스가 지나쳐 탐색이 끝나게 되면
          // 피벗보다 큰 값과 작은값이 결정되는 경계를 rightIndex가 가리키고 있기 때문에 교환해야 함
          swap(arr, start, rightIndex);
          return rightIndex;
      }
  
      // 처음, 중간, 끝의 데이터를 비교해 중간의 값을 피벗으로 정하고 연산을 쉽게 하기 위해
      // 해당 피벗값을 가장 왼쪽 값과 교환
      private static void medianOfThree(int[] arr, int start, int end) {
          int[] index = {start, (start + end) / 2, end};
  
          if (arr[index[0]] > arr[index[1]]) {
              swap(index, 0, 1);
          }
  
          if (arr[index[1]] > arr[index[2]]) {
              swap(index, 1, 2);
          }
  
          if (arr[index[0]] > arr[index[1]]) {
              swap(index, 0, 1);
          }
  
          swap(arr, start, index[1]);
      }
  
      private static void swap(int[] arr, int idx1, int idx2) {
          int tmp = arr[idx1];
          arr[idx1] = arr[idx2];
          arr[idx2] = tmp;
      }
  }​

• 테스트
  [QuickBasicMain.java]
  

  package Sort.Quick;
  
  public class QuickBasicMain {
      private static final int MAX_COUNT = 30;
  
      public static void main(String[] args) {
          int[] arr = new int[MAX_COUNT];
          for(int i=0; i<MAX_COUNT; i++) {
              // 0 ~ MAX_COUNT 범위내의 난수를 생성
              arr[i] = (int)(Math.random() * MAX_COUNT);
          }
  
  //        int[] arr = {4, 4, 1, 2, 2};
  
          System.out.println("정렬 전 데이터");
          for(int i : arr) {
              System.out.print(i + " ");
          }
          System.out.println();
  
          System.out.println("정렬 후 데이터 (오름차순)");
          int[] quickSortTestArray = arr.clone();
          QuickBasic.sort(quickSortTestArray);
          for(int i : quickSortTestArray) {
              System.out.print(i + " ");
          }
          System.out.println();
      }
  }​

• 결과
  

  

 

 

 

참고
윤성우의 열혈 자료구조

위키