Pages

Insertion Sort

Straight insertion is a sorting method which takes a parenthesis data on ordered data and shoves data which is bigger than parenthesis data so parenthesis data can be placed on right place. For example, there is an array that contains these number :
31224135
If the data above is sorted in ascending by straight insertion, the result is:

Parenthesis DataSorting Result
12
31224135
In 1st loop, 2nd data of array becomes parenthesis data, then being compared with all previous data (3). If there is no data which is bigger than parenthesis data, there is no data that will be shove backward.
2
31224135
In 2nd loop, 3rd data of array becomes parenthesis data, then being compared with all previous data (3, 12). There are two data which are bigger than parenthesis data so those data will be shoved one step backward and put parenthesis data at 1st place.
4
23124135
In 3rd loop, 4th data of array becomes parenthesis data, then being compared with all previous data (2, 3, 12). This data will be placed at 3rd place.
13
23412135
In 4th loop, 5th data of array becomes parenthesis data, then being compared with all previus data (2, 3, 4, 12). Because there is no data that bigger than the parenthesis data so the parenthesis data still be in the 5th place.
5
23412135
In 5th loop, 6th data of array becomes parenthesis data, then being compared with all previous data (2, 3, 4, 12, 13). This data will be placed at 4th place.
Result
23451213


For implementation this sorting method, I use C program as an example.

First, I make a file that contains some numbers that will be sorted. I give its name "numberdata.txt". The numbers are separated by space.
Second, I build a source code which is placed in the same folder with "numberdata.txt". I give its name "insertionsort.c"

Here is the program in C.

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

const int ndata = 12; //number of data that will be sorted

int main()
{
   
//variables
    int array[ndata];
    int resultarray[ndata];

   
//read file "numberdata.txt"
    //put the values which is got into an array

    FILE *pers;
    pers = fopen("numberdata.txt","r");
    int m;
    for(m=0; m<ndata; m++)
    {   
        fscanf(pers,"%d",&array[m]);
        printf("%d\t",array[m]);
    }
    fclose(pers);
    printf("\n");
   
   
//put data in array into resultarray
    for(m=0; m<ndata; m++)
    {   
        resultarray[m] = array[m];
        printf("%d\t",resultarray[m]);
    }
    printf("\n");
   
   
//ascending sort using insertion method
    int n,p;
    for(m=1; m<ndata; m++)
    {
        for(n=0; n<m; n++)
        {
            if (array[m]<resultarray[n])
            {
                for(p=m; p>n; p--)
                {
                    resultarray[p]=resultarray[(p-1)];
                }
                resultarray[n] = array[m];
                break;
            }
        }
    }
   
   
//show result
    for(m=0; m<ndata; m++)
    {   
        printf("%d\t",resultarray[m]);
    }
    printf("\n");
   
    return 0;
}

You can download this work HERE.

1 comment: