This is the note for introduction of Algorithms, based on the MIT open class. The lecture 1 focus on how to measured the performance of program, and two sort algorithms has been mentioned, which is insertion sort and merging sort.

Here is the c program I wrote.I wish it could be a nice start, and whole open classes could been finished in 2013 finnally.

insertion sort

 

1 /* 2  *    Insertion sort 3  *  written by Fredric 4  *  2013-5-5 5  */ 6 #include 
      
        7 #include 
       
         8  9 #define        INPUT_LEN    610 unsigned int g_input[INPUT_LEN]11 = {
    8,2,4,9,3,6};12 13 /*14  *    show function, only for checking the result15  */16 void show_permutation(){17     for (int i = 0; i < INPUT_LEN; i++)18     {19         printf("%d", g_input[i]);20     }21     printf("\t\n");22 }23 24 /*25  *  *pinput: pointer of the input array26  *  len    : the length of input array27  */28 void insertion_sort(unsigned int *pintput, int len){29     unsigned int key = 0;30     unsigned int tmp = 0;31     int i = 0;32 33     for (int j = 1; j < len; j++)34     {35         key = *(pintput+j);36         i = j - 1;37         while ((i >= 0)&(*(pintput + i) > key))38         {39             //insert the key value40             tmp = *(pintput + i);41             *(pintput + i) = *(pintput + i + 1);42             *(pintput + i + 1) = tmp;43             44             45             i = i - 1;46         }47     }48 }49 50 void main(void){51     52     insertion_sort(g_input, INPUT_LEN);53 54     show_permutation();55 56     system("pause");57 58     return;59 }
       
      

 

Merging sort

1 /* 2 *  from   : the beginning of the array 3 *  to     : the end of the array 4 *  len    : the length of input array 5 */ 6 void merging_sort(int from, int to){ 7     int i,j,p = 0; 8  9     if (from < to)10     {11         int mid = (from + to)/2;12         13         //recursively sort14         merging_sort(from, mid);15         merging_sort(mid + 1, to);16 17         //merge 18         i = from;19         j = mid + 1;20         p = from;21         while ((i <= mid) || (j <= to))22         {23             if (i > mid)24             {25                 g_output[p] = g_input[j];26                 j++;27                 p++;28             } 29             else if (j > to)30             {31                 g_output[p] = g_input[i];32                 i++;33                 p++;34             }else{35                 if (g_input[i] < g_input[j])36                 {37                     g_output[p] = g_input[i];38                     i++;39                     p++;40                 } 41                 else42                 {43                     g_output[p] = g_input[j];44                     j++;45                     p++;46                 }47             }48         }//end of while49         50         for (int t = from; t <= to; t++)51         {52             g_input[t] = g_output[t];53         }54     }55 56     return;57 }