Insertion Sort

Two Insertion Sorts are Different in Code.

Code-1

//第一迴圈
//用於判定當前應該在何位置進行排序 
for(l=1;l < size;l++){

    //第二迴圈
    //用於判定該位置是否需要排序 
    for(j=0;j <= l;j++){
        //判定是否排序                               
        if(*(data+l) < *(data+j)){
            //進行排序前置動作-暫存 
            tmp_sort=*(data+l);
                
            //將除了第一迴圈所指定的數字外，將其他大於第二迴圈所指定的數字往後移 
            for(k=l;k > j;k=k-1){
                *(data+k)=*(data+(k-1));                
            }
                
            //將第二迴圈所指定的位置插入先前暫存的數字 
            *(data+j)=tmp_sort;
                
            // 避免繼續第二迴圈繼續進行 
            break;
        }
    }
}

---

Code-2

//第一迴圈
//用於判定當前應該在何位置進行排序 
for(l=1;l < size;l++){
    //暫存 
    tmp_sort=*(data+l); 
    j=l;
    //當暫存小於 j-1 之指標位置之值並且 j 大於等於 0 時 
    while((tmp_sort < *(data+(j-1)) && (j >= 0))){
     //排序數字往後移 
     *(data+j)=*(data+(j-1));
     //j 移動 
     j--;         
    }
    //將 j 之指標位址複寫為暫存之數值 
    *(data+j)=tmp_sort;
}

---

Code-1 和 Code-2 最主要的差別在於 Code-1 事先不知道需排列的陣列是不是屬於 Increase 的狀態底下，而 Code-2 則是默認為皆屬 Increase 下進行，所以當編譯後執行排列所產生的時間：

Increase
Code-1 : 隨排序量增加
Code-2 : 趨近於不需要時間

但是在 Decrease 的情況底下， Code-2 所需要的時間就會比 Code-1 還要來得多。