# 3.1.2. Quick Sort

Pivot strategy

1. Divide

• Select a pivot element, and then divide the array into two subarrays such that ....

2. Conquer

• sort each subarray recursively.

3. Combine

• do nothing.

A simple implementation

// Sort a list from A[left] to A[right].
// Should be optimized for higher efficiency!!!

void **quick_sort**(item_type *A, int left, int right) { 
  int pivot;
  if (right - left > 0) {
    //divide
    pivot = partition(A, left, right);
    //conquer
    quick_sort(A, left, pivot - 1);
    quick_sort(A, pivot + 1, right); 
  }
}

#define SWAP(a, b) { 
  item_type tmp; 
  tmp = a; 
  a = b; 
  b = tmp; 
}

int partition(item_type *A, int left, int right) { 
  int i, pivot;
  pivot = left;
  for (i = left; i < right; i++) {
    if (A[i] < A[right]) {
      SWAP(A[i], A[pivot]);
      pivot++;
      //How is the pivot element chosen in this function?  
    } 
  }
  SWAP(A[right], A[pivot]);
  return(pivot);
}

Cost

• T(n) = T(m_1) + T(m_2) + cn (m_1 + m_2 = n-1) if n>1
• T(1) = 1

Analysis |Quick Sort ||| |---|---|---| |Divide| Conquer| Combine| |O(n)|T(m_1)+T(m_2)|O(1)|

Worst-case time complexity

• 매 단계에서 선택한 pivot element가 가장 크거나 가장 작을 경우,
• T(n) = T(0) + T(n-1) + cn, T(1) = 1 then T(n) = O(n^2)
• Skewed vs well-balanced trees

Average-case time complexity

• T(n) = \sum_{p=1}^n {T(p-1) + T(n-p)} + cn
• T(0) = 1 \rightarrow
• \therefore T(n) = O(n log n)

n \leq 0, \forall n \in \mathbb{Z}, T_{ave}(n) 을 n 개의 원소를 가지는 배열을 퀵 정렬 방법을 사용하여 정렬하는데 걸리는 평균 수행시간이라고 하자. 그러먼 어떤 양의 정수 b와 c에 대해 다음과 같은 재귀 관계 존재

T_{ave} (n) \geq cn + \frac {1}{n} \sum_{p=1}^{n} \{ T_{ave} (p-1) + T_{ave} (n-p) \} \\= cn + \frac{2}{n} {\sum_{p=0}^{n-1} {T_{ave}(p)}} \forall n \geq 2

T_{ave} (1) \leq b

T_{ave} (0) \leq b

Cost_{ave} = \sum_{p=1}^n {P_r (p) \cdot Cost(p)} = \frac {1}{n} \sum_{p=1}^n {... + ...}

k=2(b+c) 라 할 때, 2보다 같거나 큰 모든 정수 n 에 대하여 T_{ave} (n) \leq kn \log_e n 과 같은 관계 존재

증명: 위의 부등식을 수학적 귀납법을 사용하여 증명하자.

1. n=2

   • 첫 번째 사실로부터 다음과 같은 관계 성립 \\ T_{ave}(2) \leq 2c + T_{ave} (0) + T_{ave} (1) \leq 2(b+c) \leq k \cdot 2 \ log_e 2
   • \therefore 따라서 두 번째 사실 성립

2. 3보다 같거나 큰 임의의 n 이 given

   • Assume that : m<n 인 모든 m 에 대하여 두 번째 사실 성립한다고 가정하자.

   • 그러면 첫 번째 사실과 이 과정을 사용하여 다음과 같은 관계 유도 가능

   • T_{ave} (n) \leq cn + \frac {2} {n} \sum_{m=0}^{n-1} {T_{ave} (m)} \\ = cn + \frac 2 m \{ T_{ave} (0)+T_{ave} (1) \} + \frac {2} {n} \sum_{m=2}^{n-1} {T_{ave} (m)} \\ \leq cn + \frac {4b} n + \frac {2k} n \sum_{m=2}^{n-1} {m log_e m}

   • 그러므로 T_{ave} (n) \leq cn + \frac {2} {n} \sum_{p=0}^{n-1} {T_{ve} (p)} \forall n \geq 2

함수 $x \log_e x$가 $x$에 대하여 아래로 볼록한 함수이어서 m log_e m \leq \int_m^{m+1} x \log_e x dx 라는 사실을 이용하면 다음과 같은 관계식을 얻는다.

• T_{ave} (n)= cn + \frac {4b}n + \frac {2k}n \int_2^n x log_e x dx \\ \leq cn + \frac {4b}{n} + \frac{2k}{n} \{ \frac{n^2 log_e n}{2} - \frac {n^2} 4 \} \\= knlog_e n + \{ cn + \frac{4b} n - \frac {kn} 2\}

$\int_2^{n x log_e x dx =[\frac 1 2 x}2 log_e x - \frac {x^{2} 4]_2}n $

= (\frac {n^2} 2) log_e n - \frac {n^2} 4 - (2log_e 2 - 1) \leq \frac {n^2} {2} {log_e n} - \frac {n^2} {4}

이 때, $ cn + \frac{4b} n - \frac 2 = (c-\frac k 2 )n + \frac {4b} n = b(\frac 4 n -n)$ 과 같고 이 값은 2보다 같거나 큰 n에 대해 항상 0보다 같거나 작으므로 T_{ave} (n) \leq kn log_e n 이 되어 3보다 같거나 큰 임의의 n에 대해서도 두 번째 사실이 성립한다. 따라서 2보다 같거나 큰 모든 정수 n에 대해 다음과 같은 두 번째 사실이 성립한다.

How can you select a “good” pivot element?

• Choose a random element in the list.
• Choose the median of the first, middle, and final elements in the list.
• Choose the median of the entire elements in the list. (bad idea)
• Etc.

Program 7.4. improved quicksort

• Choosing the median of the first, middle, and final elements as the partitioning element and cutting off the recursion for small subfiles can significantly improve the performance of quicksort.

• This implementation partitions on the median of the first, middle, and final elements in the array (otherwise leaving these elements out of the partitioning process).

• Files of size 11 or smaller are ignored during partitioning; then, insertion from is used to finish the sort.

  #define M
  
  void quicksort(ITEM[] a, int l, int r)
  {
      if (r - l <= M)
          return;
      exch(a, (l + r) / 2, r - 1);
      compExch(a, l, r - 1);
      compExch(a, l, r);
      compExch(a, r - 1, r);
      int i = partition(a, l + 1, r - 1);
      quicksort(a, l, i - 1);
      quicksort(a, i + 1, r);
  }
  
  void sort(ITEM a[], int l, int r)
  {
      quicksort(a, l, r);
      insertion(a, l, r);
  }

How can you minimize the bookkeeping cost involved in the recursive calls?

• Much of the pushing and popping of the frame stack is unnecessary.

• Lists of size smaller than M are ignored during quick sort, then do a single sorting pass at the end.

• Avoid making the recursive call on the larger subrange.  The depth of recursion <= O(log n)

  quicksortTRO(E, first, last)
  {
    int first1, last1, first2, last2;
    first2 = first;
    last2 = last;
    while (last2 - first2 > 1)
    {
  
        pivotElement = E[first];
        pivot = pivotElement.key;
        int splitPoint = partition(E, pivot, first2, last2);
        E[splitPoint] = pivotElement;
        if (splitPoint < (first2 + last2) / 2)
        {
            first1 = first2;
            last1 = splitPoint - 1;
            first2 = splitPoint + 1;
            last2 = last2;
        }
        else
        {
            first1 = splitPoint + 1;
            last1 = last2;
            first2 = first2;
            last2 = splitPoint - 1;
        }
        quicksortTro(E, first1, last1); 
        // continue loop for fist2, last2.
    }
    return;
  }

By courtesy of David R. Musser

Average-case:O(n log n)

Worst-case: O(n^2)