Algorithm | Sort : 퀵 정렬

퀵 정렬(Quick Sort) ?

출처  https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

 퀵 정렬은 분할 정복 알고리즘의 하나로 피벗(pivot)을 정한 뒤 피벗의 위치를 확정해가며 정렬한다. 피벗을 선정하는 기준은 가장 왼쪽, 가장 오른쪽, 가운데, 랜덤 등 다양하며 어떤 피벗이 좋은 피벗인지는 확답할 수 없다. 분할 정복은 대개 재귀호출을 이용하여 구현한다.

* 분할 정복 알고리즘 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략

 

퀵 정렬은 O(nlog2n)의 시간복잡도를 가지는 매우 효과적인 정렬 알고리즘으로, 자바 스크립트의 배열 객체의 내장 함수인 sort의 내부 구조도 퀵 정렬을 따른다. 

 

 퀵 정렬의 과정은 다음과 같다. 각 반복 과정에서는 재귀호출이 사용된다.

 

1. 배열의 안에 있는 요소 하나를 선택한다. 이 때 선택된 요소를 피벗(pivot)이라 한다. 

2. 피벗을 중심으로 피벗보다 작은 원소는 왼쪽으로, 큰 요소는 오른쪽으로 옮긴다.

3. 피벗의 왼쪽 배열과 오른쪽 배열에서 1 - 2번을 반복한다.

4. 배열의 크기가 1이나 0이 될 때 까지 반복한다.

퀵 정렬 구현(in JAVA)

package quick;

public class QuickSort {

  private void swap(int[] arr, int i1, int i2) {
    int temp = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = temp;
  }

  private int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int low = left + 1;
    int high = right;
    while(low < high) { // low와 high가 교차할 때까지 반복
      // low가 pivot보다 작으면 계속 오른쪽으로 이동.
      while(arr[low] < pivot) low++;

      // high가 pivot보다 크다면 계속 왼쪽으로 이동.
      while(arr[high] > pivot) high--;

      // 왼쪽과 오른쪽 이동이 끝난 경우는 pivot < arr[low] && pivot > arr[high]인 경우다.
      // 이 때는 두개의 값을 교환해준 후 다시 low와 high를 이동한다.
      if(low < high) { 
        swap(arr, low, high);
      }
    }

    // 피벗을 정렬된 배열에 가운데에 끼운다.
    swap(arr, high, left);
    
    return high;
  }

  public void quickSort(int[] arr, int left, int right) {
    if(right - left <= 1) { // 리스트의 사이즈가 0이나 1일 경우 재귀단계 종료
      return;
    }

    int pivot = partition(arr, left, right);

    quickSort(arr, left, pivot-1);  // 왼쪽 정복
    quickSort(arr, pivot+1, right); // 오른쪽 정복
  }
}

 

 배열의 가장 왼쪽 요소를 피벗으로 선택하도록 구현해보았다. 퀵 정렬의 과정은 크게 분할과정인 'partition()'과 정복과정인 'quickSort()'로 나뉜다.

 

1. 분할 과정 - partition()

출처  https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

2. 정복 과정 - quickSort()

 분할 과정의 결과 제 위치를 찾은 피벗을 기준으로 왼쪽과 오른쪽이 나뉘게 되고 다시 나뉜 두 배열을 배열의 크기가 0이나 1이 될 때 까지 분할 과정을 반복하여 정복한다.

---

Reference

 

· 퀵 정렬이란? - https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

· 퀵정렬 5분만에 이해하기 - https://www.youtube.com/watch?v=cWH49IKDIiI