퀵 정렬(Quick sort)

: pivot(보통 가운데 값)을 기준으로 좌우 구간으로 나눠 정복(분할, 정복).

• e.g. 오름차순의 경우, pivot 왼쪽엔 pivot보다 작은 값을, 오른쪽엔 큰 값을 위치하도록 partition. 또 이렇게 나뉜 좌 우 배열을 다시 quick sort 수행(분할). 이 때 pivot 값은 해당 부분 배열에서 이미 본인의 위치를 찾은 것이기 때문에(정복) 재귀에 포함하지 말 것.
• 기본적으로 재귀를 사용하기 때문에 Stack 자료구조의 개념이 사용된다고 보면 됨
• 안정적인 정렬이 아니다.
  • 중복 값이 있다고 가정했을 때 pivot과 같은 값인 경우 pivot의 위치가 해당 element 위치를 역전 가능

시간복잡도

• 평균적으로 O(Nlog(N)) 이지만, 최악의 경우 O(N^2)가 된다.
  • n log n == n(n개의 element에 대해 비교연산) * log n(비교의 깊이)
• 최악의 경우: pivot에 해당하는 값이 항상 부분 배열내에서 가장 작거나 가장 커서 원소 n개에 대해서 각 호출을 n번, n-1번, n-2번 … 계속 수행해야한다. 따라서 이 경우 O(N^2)
  • 방지하는 방법 ? 특정 위치의 원소를 정하지 말고 가운데의 값을 갖는 pivot을 지정하면 된다.
    • 그런데 어떻게? - 물리적 가운데 값이 데이터의 중간이라고 보장할 수는 없을 것 같은데
    • 대부분의 실 데이터들은 가운데값이면 가운데에 분포되어있다.(한쪽으로 편향된 경우는 거의 없다)

퀵 소트의 지역성(locality)

: 가까운 공간의 데이터에 반복적으로 접근한다는 성질. merge sort와 같은 시간복잡도를 가지지만, 일반적으로 지역성의 특징때문에 퀵 소트가 성능이 좋다고 한다.

• 가상 메모리의 관점에서, 참조의 지역성이라는 성질을 효율좋게 이용하기 위해 자주 사용되는 페이지와 인접하게 있는 페이지(메모리)는 캐싱된다. 이는 물리 메모리까지 접근하지 않아도 되기 때문에 이득이다.
• 처음부터 끝까지, 심지어 새로운 배열을 할당해야하는 merge sort와 달리, quick sort는 제자리 정렬 알고리즘이며, pivot을 기준으로 인접한 주소의 메모리를 참조해 swap하는 방식이다. 따라서 quick sort가 이러한 특성을 잘 이용한 알고리즘이다.

소팅 과정

1. 초기 pivot: 5(맨 앞)을 기준으로 수행. 해당 pivot 제외 가장 좌측 low, 가장 우측 high로 접근
2. high에서 왼쪽으로 가면서 pivot보다 작은 것 있으면 stop, low에서 오른쪽으로 가면서 pivot보다 큰 값 있으면 stop
   • 둘다 stop한 상황에서 둘이 교체하고, 다시 진행
   • high < low 가 되었을 때 high와 pivot을 교체(pivot이 왼 쪽에 있는 경우였기 때문에)
3. pivot을 기준으로 좌, 우 서브 배열로 나눠 2번의 과정을 각각 진행한다.(재귀적으로)

int quickSort(int* data, int start, int end) {
  if(start == end) // size of data is 1.
    return;
  
  int pivot = start;
  int low = start + 1, high = end;
  while(1) {
    while(start < high && data[pivot] < data[high])
      high--;
    
    while(low <= end && data[low] < data[pivot])
      low++;
    
    if(high < low)
      break;
    
    int tmp = data[high];
    data[high] = data[low];
    data[low] = tmp;
  }
  
  int tmp = data[high];
  data[high] = data[pivot];
  data[pivot] = tmp;
  
  quickSort(data, start, high - 1);
  quickSort(data, high + 1, end);
}

Reference)

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Algorithm

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