끄적끄적 코딩
article thumbnail

https://en.wikipedia.org/wiki/Quicksort

 

개념

하나의 리스트를 피벗을 기준으로 분할하고 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬하는 과정을 반복한 다음, 
정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법

컴퓨터로 가장 많이 구현된 정렬 알고리즘 중 하나
다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬
같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬
퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬
합병 정렬(Merge Sort)와 달리 퀵 정렬은 리스트를 비균등하게 분할

속도가 빠름
정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 수행시간이 오래 걸림


1. 리스트 가운데서 하나의 원소를 고른다. (이렇게 고른 원소 = 피벗)

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

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

 

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

 

시간 복잡도

Worst Case - O(n^2)
Best Case - O(n log n)
Average Case - O(n log n)

Worst Case => 이미 정렬된 경우, 피벗을 가장 크거나 작은 값들만 고르는 경우

 

예제 코드

void quickSort(int i, int j)
{
  if (i >= j)
  {
    return;
  }

  int pivot = array[(i + j) / 2];
  int left = i;
  int right = j;

  while (left <= right)
  {
    while (array[left] < pivot)
    {
      ++left;
    }
    while (array[right] > pivot)
    {
      --right;
    }
    if (left <= right)
    {
      swap(array[left], array[right]);
      ++left;
      --right;
    }
  }

  quickSort(i, right);
  quickSort(left, j);
}

검색 태그