[알고리즘] 정렬5: quick sort

Quick Sort

시간복잡도 : O(Nlog_2N) 이지만 최악의 경우는 마찬가지로 O(N^2)

퀵 정렬은 아주 빠른 속도를 나타낼뿐만 아니라 원리도 간단해서 많은 응용 분야에서 사용되고 있다.
퀵 정렬은 연속적인 분할에 의해서 정렬한다.

축(Pivot)값을 중심으로 왼쪽은 이 축값보다 작은 값으로 오른쪽은 모두 이 축값보다 큰 값을 배열시키는 것이다.
이렇게 하여 축값의 왼쪽과 오른쪽 부분을 각각 또다시 분할하고 하는 과정을 분할의 크기가 1이 될 때까지 반복하면 전체적으로는 정렬이 완료된다.

-리스트 마지막 인덱스의 값을 pivot으로 정함.
피봇을 뺀 나머지 배열에서 가장 양쪽 끝 인덱스를 저장. 왼쪽은 i, 오른쪽은 j (인덱스 2개 사용)
i는 오른쪽으로 가면서 해당 값이 pivot보다 작아야 한다. 큰 것이 발견되면 멈춤.
j는 왼쪽으로 가면서 해당 값이 pivot보다 커야 한다. 작은 것이 발견되면 멈춤.
i위치와 j위치의 값을 바꿈.
그런데, i, j가 만나게 되는 경우. (i>=j) 해당 위치가 pivot이 들어갈 자리.
i위치의 값과 pivot 값 swap한다.
pivot을 기준으로 왼쪽, 오른쪽으로 리스트를 나누어, 각각 처음부터 다시 소팅한다.

알고리즘

1. 만약 n>1 이면
2. 1 N 크기의 a 배열을 분할 하여 축값의 위치를 mid로 넘긴다.
3. 2 퀵 정렬 알고리즘(a, mid)
4. 3 퀵 정렬 알고리즘 (a+mid-1, N-mid-1)

void quick_sort(int a[], int n){
    int v, t;
    int i, j;
    if (n > 1){
        v = a[n - 1]; // v=축값. 마지막 노드값을 사용
        i = -1; 
        j = n - 1; 
        while (1){ // 분할
            while (a[++i] < v); // 왼쪽에서부터 축값보다 크거나 같은 값이 있는지?
            while (a[--j] > v){ // 오른쪽에서부터 축값보다 작거나 같은 값이 있는지? -> 가장작은값이 pivot이면?? index out range 위험 아래 체크 필요.
                if (j==0) break ;
            }
            if (i >= j) break; // i와 j의 위치가 뒤바뀌었으면 분할 끝
            t = a[i]; // 아니면 두 값을 바꿈
            a[i] = a[j];
            a[j] = t;
        }
        t = a[i]; // 축 값과 축값의 위치에 있는 값을 바꿈
        a[i] = a[n - 1];
        a[n - 1] = t;
        quick_sort(a, i); // 왼쪽 구간 퀵정렬
        quick_sort(a + i + 1, n - i - 1); // 오른쪽 구간 퀵정렬
    }
}

퀵 정렬은 난수 배열이나 반쯤 정렬된 배열에 대해서는 빠른 속도를 보이지만 이미 정렬된 배열이나 역순 배열에 대해서는 성능이 엄청나게 떨어진다.
퀵 정렬의 이상적인 경우는 분할이 정확하게 구간을 양분하는 것이다. 이 경우 재귀의 깊이는 logN이 되며 가장 빠른 속도를 나타낸다.
이렇게 퀵 정렬은 분할할 축값이 어느 정도 그 구간의 중앙을 나누느냐에 성능이 좌우된다.
재귀 호출로 인해서 내부 스택이 사용된다. 따라서 퀵 정렬이 속도가 빠른 반면에 메모리의 희생이 있다.
N이 커지면 커질수록 스택의 크기가 커지며 스택 오버플로우가 발생할 수 있다.

성능개선: 이미 정렬된 상태인지를 체크하는 것을 추가한다.

ex)

0,1,2,3,4,5,6,7,8 : 인덱스
5,3,8,4,9,1,6,2,7 : 값

qsort

1. 피봇을 마지막 번째 노드 값으로 정하자. (보통 첫번째나 마지막번째로 정함.)
   남은 데이터의 양쪽 끝에서 가운데로 스캔해 나가면서 왼쪽에서는 피봇보다 큰 값을 찾으면 멈추고, 오른쪽에서는 피봇보다 작은 값을 찾으면 멈추고, 둘을 교환한다.

pivot=7, scan index=0, 7 start find over or below than pivot.
stop index=2(큰값발견),7(작은값발견) value 8>7>2 ;swap
0,1,2,3,4,5,6,7,8
5,3,2,4,9,1,6,8,7

pivot=7, stop index=4, 6 value 9>7>6 ;swap
0,1,2,3,4,5,6,7,8
5,3,2,4,6,1,9,8,7

pivot=7, stop index=6> 5 ; cross
stop. index=5, 4 인덱스가 교차되면 멈추고, 피봇(오른쪽 파트위치로 인덱스를 잡았으므로 right part에 속해야 한다. left part의 마지막 스캔 위치 인덱스6, 피봇보다 큰 수를 처음 발견한 지점에 들어가야 한다. )과 left last index(6)와 swap
0,1,2,3,4,5,6,7,8
5,3,2,4,6,1,7,8,9
피봇을 기준으로 좌우 분리가 끝남.
피봇 위치가 바뀌면 한 싸이클이 끝난 것임. (pivot 7을 기준으로 좌(low)우(high) 분리 완료)

2. 좌우 파트("532461", "89")에 대해 각각 qsort 수행. 파트의 원소 개수가 1이면 스킵.
   2-2.
   0 1 (실제 인덱스는 7,8)
   8 9
   pivot=9, stop=N, 0. 왼쪽값을 찾지 못함. 즉, 모두 작다. 이미 피봇은 가장 우측이라 변경할 필요가 없다. 리턴

2-1.
0,1,2,3,4,5
5,3,2,4,6,1
new pivot=1, start 0, 4

pivot=1, stop 0, N; 왼쪽에서는 큰 값을 찾았는데, 오른쪽에서는 작은 값을 찾지 못함. left part last index=0과 swap
0,1,2,3,4,5
1,3,2,4,6,5

3. 좌우 파트 수행 : "", "32465". 왼쪽 파트는 1개이하라 스킵. 오른쪽 파트 수행
   0 1 2 3 4 (실제 인덱스 : 1,2,3,4,5)
   3 2 4 6 5
   new pivot=5 ; start 0, 3
   pivot=5, stop=3>2.cross! last left index=3. change
   0 1 2 3 4 (실제 인덱스 : 1,2,3,4,5)
   3 2 4 5 6

4. 좌우 파트 수행 : "3 2 4", "6" ; 오른쪽 파트는 스킵.
   0 1 2 (실제 인덱스 : 1,2,3)
   3 2 4
   pivot=4, stop=N, 1 no swap. break

5. 좌우 파트 수행 "32", ""
   0 1 (실제 인덱스 : 1,2)
   3 2
   pivot=2, start=0,0
   pivot=2, stop=0, N ; swap with index 0
   0 1 (실제 인덱스 : 1,2)

2 3
6. 좌우 분할 ; "", "3" ; 모두 리턴

0,1,2,3,4,5,6,7,8 : 인덱스
1,2,3,4,5,6,7,8,9 : 값

vector<double>  QuickSort(vector<double>& vec1){
  double i =  0;
  double j = vec1.size()-2;
  double tmp;
  int pivotindex = vec1.size()-1  ;
  double pivot = vec1[pivotindex];
  if  ( vec1.size()<=1  )
    return vec1 ;
  cout <<  "QuickSort: ";
  printvector(vec1)  ;

  while  (i <= j)  {
    while  (vec1[i]  < pivot)
      i++;
    while  (vec1[j]  > pivot)
      j--;
    if  (i <= j)  {
      tmp = vec1[i];
      vec1[i]  = vec1[j];
     vec1[j]  = tmp;
     i++;
     j--;
    }
  }

  // pivot change
  vec1[pivotindex]  = vec1[i]  ;
  vec1[i]=pivot ;
  pivotindex=i ;

  cout <<  "pivotting: ";
  printvector(vec1)  ;

  if  (vec1.size()<=2  )
       return vec1 ;

    // partition
    vector<double> left_vec, right_vec ;
    vector<double>::iterator pivotiter = vec1.begin()+pivotindex ;
    copy(vec1.begin(), pivotiter, back_inserter(left_vec))  ;
    copy(pivotiter+1, vec1.end(), back_inserter(right_vec))  ;

    cout <<  "left: ";
    printvector(left_vec)  ;
    cout <<  "right: ";
    printvector(right_vec)  ;

    if  (left_vec.size()>0  )  {
        QuickSort(left_vec);
        copy(left_vec.begin(), left_vec.end(), vec1.begin())  ;
    }

    if  (right_vec.size()>0  )  {
        QuickSort(right_vec);
        copy(right_vec.begin(), right_vec.end(), pivotiter+1)  ;
    }
    return vec1;
}