Sorting Algorithm

程式的基本功

Insertion Sort

　　是一種最簡單基本、容易理解的排序演算法。
基本概念：利用最直觀的方法，將新的元素插入至前面已排序好的數列中排序。
也就是將第i筆record插入到前面(i-1)筆record已sortec之list中(i=2 to n 做(n-1)回合)(loop)，成為i筆已sorted之串列。

Principle

  • 通常不會使用額外的數列記錄已排序好的數列。
    • 　
  • 將數列分成兩部分：未排序及已排序。

    • Complexity

    Time complexity:

    1. Best case:O(n)。
      情況為input data恰巧由小->大呈現。(只需n-1次比較)
    2. Worst case:O(n2)。
      情況為input data恰巧由大->小呈現。(第i回合需比i次)
    3. Average case:O(n2)。
      T(n)=T(n-1)+c*n,T(1)=0
      T(n)=c*(n+2)(n-1)/2 => O(n2)。
    Space complexity:
    　　O(1)。(除了input data space以外之需求是固定的)

    運算流程

    1. 從未排序部分的數列取出一元素。
    2. 由左向右和已排序部分的數列做比較，直到遇到不大於自己的元素並插入此元素之後；若沒有則插入至最左邊。
    3. 重複以上動作1->2直到未排序部分的數列全部處理完成。

    Stable vs. Unstable sort

    Stable。
    ex: Input:...,5,...,5*,...
    因5* !< 5 所以排序後仍為...,5,...,5*,...。

    簡易code

    1. Insert(list,r,i)
    2. Insort(list,n)

    //將record r 插入到list[0]~[i]已sorted之list中，成為sorted list
    I. Insert(list,r,i)
    { j=i;
    　while(r<list[j])do
    　　{ list[j+1]=list[j];
    　　　　j=j-1;
    　　}
    　　list[j+1]=r;　　//r置入正確位置
    }

    簡易code

    II. Insort(list,n)
    //排序list[1]~[n] records
    { list[0]= -∞
    　for i=2 to n do
    　　Insert(list, list[i], i-1)
    }