[알고리즘] 정렬 - quick sort

퀵소트

- 불안정정렬, 비교정렬

- divide and conquer 사용

 

이름이 퀵소트인지라 best case에선 가장 빠른 시간복잡도를 가지지만 worst case에선 한없이 느려지는....양날의 칼느낌이다. 그냥 머지소트를 쓰는 걸로 하자.

 

시간 복잡도 

best case O(n log n)

worst case O(n^2)

 

worst case는 어떤 경우냐 하면
오름차순 정렬인데 5 4 3 2 1로 배열이 제시되었을 경우이다.

 

퀵 소트의 구현 과정을 살펴보면 이해 가능하다.

 

퀵소트는

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

1. pivot이 있고 (보통 배열 왼쪽 끝 혹은 오른쪽 끝 값)

2. 피벗을 중심으로 좌측엔 피벗보다 작은값, 우측엔 피벗보다 큰 값을 배치한다.

 

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

3. 작은값, 큰 값 교차 지점에 피벗을 놓는다.

 

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

4. 피벗을 중심으로 배열을 반으로 갈라서 왼쪽 오른쪽 부분 배열에 대해 1,2,3과정을 실시!

 

 

코드

#include <stdio.h>
#include <algorithm>

using namespace std;

void quicksort(int arr[], int left, int right)
{
  if (left >= right)
  {
    return;
  }

  int pivot = arr[left];
  int i = left, j = right;

  while (i < j)
  {
    while (pivot < arr[j])
    {
      j--;
    }

    while (i < j && pivot >= arr[i])
    {
      i++;
    }

    swap(arr[i], arr[j]);
  }
  swap(arr[left], arr[i]);

  int pi = i;
  quicksort(arr, left, pi - 1);
  quicksort(arr, pi + 1, right);
}

int arr[1000000];
int main(void)
{
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    scanf("%d", &arr[i]);
  }

  quicksort(arr, 0, n - 1);
  for (int i = 0; i < n; i++)
  {
    printf("%d\n", arr[i]);
  }
  return 0;
}

 

참고:

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