[알고리즘] 퀵 정렬 (Quick sort) - 자바 Java

[ 개념 ] 

- 분할 정복(divide and conquer) 방법을 통해 주어진 배열 정렬

- 불안정 정렬, 비교 정렬

📍 분할 정복 (divide and conquer)
: 문제를 작은 2개의 문제로 분리하고 각각을 해결한 후, 결과를 모아 원래의 문제를 해결하는 방법

[ 과정 설명 (오름차순) ] 

- 배열 가운데 하나의 원소를 고르며, 그 원소를 pivot 이라고 함(피벗을 기준으로 비균등하게 2개의 부분 배열로 분할)
- 피벗을 기준으로 피벗 앞에는 피벗보다 작은 수가, 오른쪽에는 피벗보다 큰 수가 옮겨짐
- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬(피벗을 다시 선택해 정렬을 반복)
- 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복

[초기 배열]
6 9 20 3 5 10 7 11 15 1

 

1) 배열의 가장 왼쪽의 숫자를 피벗값으로 설정

6 9 20 3 5 10 7 11 15 1

 

2) 피벗값을 기준으로 나머지 값들에 대해 왼쪽부터는 피벗값보다 큰 값을, 오른쪽부터는 피벗값보다 작은 값을 찾음
     큰 값은 9, 작은 값은 1으로 둘의 위치를 교환해 주고 반복

6 9 20 3 5 10 7 11 15 1

6 1 20 3 5 10 7 11 15 9

6 1 20 3 5 10 7 11 15 9

6 1 5 3 20 10 7 11 15 9

 

3) 큰 값의 인덱스가 작은 값의 인덱스보다 더 높아지면 둘 중 작은 값을 피벗값과 교환, 이 때 피벗값은 정렬위치가 확정

3 1 5 6 20 10 7 11 15 9

 

4) 6의 왼쪽 집합과 오른쪽 집합에서 각각 첫 번째 요소를 피벗으로 지정하고 두 집합의 퀵 정렬을 동시에 수행

3 1 5 6 20 10 7 11 15 9

3 1 5 6 20 10 7 11 15 9

1 3 5 6 20 10 7 11 15 9

1 3 5 6 20 10 7 11 15 9

1 3 5 6 20 10 7 11 15 9

1 3 5 6 9 10 7 11 15 20

1 3 5 6 9 10 7 11 15 20

1 3 5 6 9 10 7 11 15 20

1 3 5 6 9 7 10 11 15 20

1 3 5 6 7 9 10 11 15 20

1 3 5 6 7 9 10 11 15 20

1 3 5 6 7 9 10 11 15 20

[ 코드 예시 (오름차순) - 자바 Java ]

public class QuickSort {

  public static void main(String[] args) {
    int[] arr = { 3, 1, 5, 6, 20, 10, 7, 11, 15, 9 };
    quickSort(arr);
  }

  public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
  }

  private static void quickSort(int[] arr, int start, int end) {
    // start가 end보다 크거나 같다면 정렬할 원소가 1개 이하이므로 정렬하지 않고 return
    if (start >= end)
      return;
    
    // 가장 왼쪽의 값을 pivot으로 지정, 실제 비교 검사는 start+1 부터 시작
    int pivot = start;
    int lo = start + 1;
    int hi = end;
    
    // lo는 현재 부분배열의 왼쪽, hi는 오른쪽을 의미
    // 서로 엇갈리게 될 경우 while문 종료
    while (lo <= hi) {
      while (lo <= end && arr[lo] <= arr[pivot]) // 피벗보다 큰 값을 만날 때까지
        lo++;
      while (hi > start && arr[hi] >= arr[pivot]) // 피벗보다 작은 값을 만날 때까지
        hi--;
      if (lo > hi)				 // 엇갈리면 피벗과 교체
        swap(arr, hi, pivot);
      else
        swap(arr, lo, hi);			 // 엇갈리지 않으면 lo, hi 값 교체 
      }
	
    // 엇갈렸을 경우, 
    // 피벗값과 hi값을 교체한 후 해당 피벗을 기준으로 앞 뒤로 배열을 분할하여 정렬 진행
    quickSort(arr, start, hi - 1);
    quickSort(arr, hi + 1, end);

  }

  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}