Insertion Sort (插入排序法)

(一) Concept:
  將第 i 筆 record 插入到前面 (i-1)筆 已經sorting 之list中，形成 i 筆已經排序好的list ie...i=2 to n 共執行 n-1回合。

(二)example:{88,7,87,9,80,100,800,10,5}

(三)每回合變化

 



程式碼:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main (void)
{
    int k;
    int a[] = {88,7,87,9,80,100,800,10,5}; //You change the data what you want to sort
    int array_size = sizeof(a)/sizeof(int);


    printf("start Insertion sort\n");
    InsertionSort(a,array_size);


    printf("Ans is:");
    for(k = 0; k<array_size;k++) //print the result
        printf("%d ",a[k]);


}

void InsertionSort(int data[],int array_size)
{
    int i,j,index,q;
    int counta = 0;
    bool f;

    for(i=1; i< (array_size); i++) //execute the n-1 times
    {
        index = data[i];

        for(j=i;j>0&&data[j-1]>index;j--)//假如後者大於前者則對調
        {
            data[j] = data[j-1];
        }

        data[j] = index;
/*
     // print the every pass
        printf("pass%d ",i);
        for(q=0;q<array_size;q++)
            printf("%d ",data[q]);
        printf("\n");*/


    }

}