Sorting Algorithm

程式的基本功

Quick Sort

　　是一高等排序演算法，又稱為Partion Exchange Sort，具有最佳的平均執行時間，也是目前公認效率最高的排序演算法。
基本概念：與merge sort相類似，皆利用Divide and conquer algorithms來解決問題。就是把一複雜問題拆解成兩個 或更多的相同或相似的子問題，直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合併。
　　主要是從數列中挑出一元素pivot做基準，把數列分成大於pivot及小於pivot的兩個子問題，依序循環完成排序。

Principle

  • 使用Divide and conquer algorithms。
    • 　
  • 選出一pivot。

    • Complexity

    Time complexity:

    1. Best case:O(n log n)。
      情況為選定之pivot恰巧切割數列成兩等分。
      T(n)=c*n+T(n/2)+T(n/2)
      =c*n log n => O(n log n)
    2. Worst case:O(n2)。
      情況為選定之pivot恰巧是數列中最大或最小的元素，數列便呈現小->大或大->小的情況。
      T(n)=c*n+T(0)+T(n-1)
      =c*(n+2)(n-1)/2 =>O(n2)
    3. Average case:O(n log n)。
      T(n)=c*n+Σ[T(s)+T(n-s)]/n
      =2c*n*logn-cn-c =>O(n log n)
    Space complexity:
    　O(log n)~O(n)
    　額外空間需求來自於Stack for recursion，而stack size需求與recursive calls次數成正比。

    運算流程

    1. 從數列中挑出一元素pivot做基準。
    2. 小於pivot的元素移至pivot的左邊，大於pivot的元素移至pivot的右邊，相等的任意放。
    3. 將pivot左邊和右邊視為兩個數列(子問題)，並對此兩數列(子問題)重複1->2動作直到數列剩下一個或零個元素。

    Stable vs. Unstable sort

    Unstable。
    ex: Input:3,5,5*,1
    pivot:3 Output:3,1,5*,5

    pivot之選擇

    quick sort的時間複雜度關鍵在於選擇pivot。正所謂：好的pivot讓你上天堂，不好的pivot讓你算到爽。
    主要原則為避免選到的pivot為最大或最小的元素，形成Worst case。

    1. 固定選擇一位置。ex:第一個、最後一個數值、中間的數值
      但此法不是很好，可能選到不好的，有點在賭運氣。
    2. 亂數。
      但此法依然不是很好，可能選到不好的，有點在賭運氣。
    3. midian-of-Three。
      挑選數列的第一個、中間的、及最後一個元素而用這三個之中的中位數 (median) 來當做 pivot。
    4. median of medians。
      數列依大小排列，挑選位置在最中間的數值，雖是最好的方法，但不容易計算，反而會增加複雜度。

    簡易code

    Qsort(list,m,n)
    //排序list[m]~list[n],且設list[n+1]必定大於list[n]
    { if m<n then
    　{ i=m;
    　　j=n+1;
    　　pk=list[m]; //pk=pivot
    　　repeat
    　　{ 　repeat
    　　　　{ i=i+1;
    　　　　until list[i]>=pk
    　　　　}
    　　　　repeat
    　　　　{ j=j-1;
    　　　　until list[j]<=pk
    　　　　}
    　　　　if i<j then swap(list[i], list[j]);
    　　until (i>=j)
    　　}
    　swap(list[m],list[j]);
    　Qsort(list,m,j-1);
    　Qsort(list,j+1,n);
    　}
    }