퀵 정렬 (Quick Sort)

퀵 정렬이란?

퀵 정렬(Quicksort)은 분할 정복 알고리즘으로, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

 

 

시간 복잡도

최악의 경우 O(n^2)

평균 O(nlogn)

 

 

진행 과정

1. 리스트에서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라고 한다.

2. 피벗 앞에는 피벗보다 값이 작은 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 원소들이 오도록 한다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에는 피벗은 더 이상 움직이지 않는다.

3. 분할된 두 개의 리스트에 대해 재귀적으로 1, 2 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복한다.

 

 

코드

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

  if(left >= right) return;

  int pivot = arr[left];

  int j = right;

  int i = left+1;

 

  while(j>=i){

    while(i<=right && pivot>arr[i]) i++;

    while(pivot<arr[j]) j--;

    if(i<j){

      int temp = arr[i];

      arr[i] = arr[j];

      arr[j] = temp;

    }

  }

  arr[left] = arr[j]

  arr[j] = pivot;

  quickSort(array, left, j-1);

  quickSort(array, j+1, right);

}

 

 

시간 복잡도를 완화시키는 방법

1. pivot의 기준을 잡을 때 난수를 사용한다.

기본적인 퀵 정렬은 피봇을 L로 잡았는데, 이렇게 되면 정렬이 되어있을 경우 O(N^2)의 시간이 걸리게 된다. 이 경우를 피하기 위해 아무 수나 피봇으로 잡은 뒤 그 수를 기준으로 퀵 정렬을 해준다. 이렇게 되면 최악의 경우(O(N^2))일 확률은 낮아지고, 절반에 비슷하게 나눠질 확률이 높아져 평균 시간복잡도가 O(nlogn)이 된다.

 

2. Median-of-Three Partition을 사용한다.

Median-of-Three Partition이란 배열의 처음, 가운데, 끝 값을 비교해 세 수끼리 정렬을 한 후 가운데 값을 피봇으로 잡아주는 것이다. 이렇게 해주면 난수를 사용하는 것과 비슷한 원리로 최악의 경우일 확률은 낮아지고, 절반에 비슷하게 나눠질 확률이 높아진다. 실제 구현된 퀵 정렬의 경우 대부분 이 방법을 사용한다.