[JAVA] 퀵 정렬 (Quick Sort)

퀵 정렬은 피벗을 기준으로 두개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 재귀적으로 수행하여 정렬하는 방법이다.

 

1. 피벗을 하나 선택한다.

2. 피벗을 기준으로 양쪽에서 피벗보다 큰 값, 혹은 작은 값을 찾는다. 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서

    부터는 피벗보다 작은 값을 찾는다.

3. 양 방향에서 찾은 두 원소를 교환한다.

4. 왼쪽에서 탐색하는 위치와 오른쪽에서 탐색하는 위치가 엇갈리지 않을 대 까지 2번으로 돌아가 위 과정을 반복한다.

5. 엇갈린 기점을 기준으로 두 개의 부분리스트로 나누어 1번으로 돌아가 해당 부분리스트의 길이가 1이 아닐 때 까지 1번

    과정을 반복한다. (Divide: 분할)

6. 인접한 부분리스트끼리 합친다. (Conqure: 정복)

 

import java.util.Arrays;
class QuickSort {
  
  private static void quickSort(int[] arr, int start, int end) {
  	int part = partition(arr, start, end);
    if(start < part - 1) quickSort(arr, start, part - 1);
    if(end > part) quickSort(arr, part, end);
  }
  
  public static int partition(int[] arr, int start, int end) {
    int pivot = arr[(start+end)/2];
    while(start <= end) {
      while(arr[start] < pivot) start++;
      while(arr[end] > pivot) end--;
      if(start <= end) {
        swap(arr, start, end);
        start++;
        end--;
      }
    }
    return start;
  }
  
  private static void swap(int[] arr, int start, int end) {
    int tmp = arr[start];
    arr[start] = arr[end];
    arr[end] = tmp;
    return;
  }
  
  public static void main(String[] args) {
    
  	int[] arr = {7,4,2,8,3,5,1,6,10,9};
    quickSort(arr, 0, arr.length-1);
    for(int i = 0; i < arr.length; i++) {
      System.out.print(arr[i]+ ",");
    }
}

출처 url: https://st-lab.tistory.com/250

자바 [JAVA] - 퀵 정렬 (Quick Sort)

https://gwang920.github.io/algorithm%20non%20ps/qucikSort/

QuickSort(퀵소트) - JAVA