[강의정리] 알고리즘 W5 (quicksort, sorting algo)

---

Quicksort

• 분할교환정렬(patition exchange sort)라고 불린다.

  void quicksort(index low, index high) {
    index pivotpoint;
    if (high > low) {
      partition(low, high, pivotpoint);
      quicksort(low, pivotpoint-1);
      quicksort(pivotpoint+1, high);
    }
  }
  
  void partition(index low, index high, index& pivotpoint) {
    index i, j;
    keytype pivotitem;
    pivotitem = S[low]; //pivotitem을 위한 첫번째 항목을 고른다.
    j = low;
    for(i = low + 1; i <= high; i++)
      if(S[i] < pivotitem) {
        j++;
        exchange S[i] and S[j];
      }
      pivotpoint = j;
      exchange S[low] and S[pivotpoint]; //pivotitem값을 pivotpoint에 넣는다
  }

분석

• 단위연산: S[i]와 key와의 비교
• 입력크기: 부분배열이 가지고 있는 항목의 수, n = high - low + 1
• 분석: 배열의 첫번째 항목만 제외하고 모든 항목을 한번씩 비교하므로, T(n) = n - 1이다.

최악의 경우 시간복잡도 분석

• 단위연산: 분할 알고리즘의 S[i]와 pivotitem과의 비교
• 입력크기: 배열 S가 가지고 있는 항목의 수, n
• 분석: 이미 비내림차순으로 정렬이 되어있는 배열을 정렬하려는 경우가 최악의 경우가 됨.

    비내림차순이면 첫번째(pivot)항목보다 작은 항목은 없으므로, 크기가 n인 배열은 크기가 0인 부분은 왼쪽에 오고, 크기가 n-1인 부분배열은 오른쪽에 오도록 하여 계속 쪼개진다. 따라서,
    T(n) = T(0) + T(n-1) - n - 1
    그런데 T(0) = 0이므로 재현식은 다음과 같이 된다.
    T(n) = T(n-1) + n - 1, n > 0이면
    T(0) = 0 
    
    이 재현식을 풀면,
    T(n) = T(n-1) + n - 1
    T(n-1) = T(n-2) + n - 2
    T(n-2) = T(n-3) + n - 3
    ...
    T(2) = T(1) + 1
    T(1) = T(0) + 0
    T(0) = 0
    
    T(n) = 1 + 2 + ... + (n-1) = n(n-1) / 2
  

평균의 경우를 고려한 시간복잡도 분석

• 단위연산: 분할알고리즘의 S[i]와 pivotitem과의 비교
• 입력크기: 배열이 S가 가지고 있는 항목의 수, n
• 분석: