facebook like button

10 December, 2011

Insertion sort in C

The need:
     This is a program to sort a given array of numbers using insertion sort. This program sorts numbers in increasing order. To read more about insert sort read wikipedia.
The code:
----------------------------------------------------------
#include<stdio.h>
void insert_sort(int a[],int size);
int main()
{
    int i,size;
    printf("program for sorting using insert sort\nHow many numbers do you want to sort\n");
    scanf("%d",&size);
    int arr[size];
    printf("enter numbers\n");
    for(i=0;i<size;i++)
    scanf("%d",&arr[i]);
    
    printf("the array before sort is\n");
    for(i=0;i<size;i++)
    printf("%d ",arr[i]);
    printf("\n");
    insert_sort(arr,size);
    printf("the array after sort is\n");
    for(i=0;i<size;i++)
    printf("%d ",arr[i]);
    printf("\n");
    return 0;
}

void insert_sort(int a[],int size)
{
    int i,j,k,temp;
    for(i=1;i<size;i++)
    {
        j=0;
        temp=a[i];
        while(temp>a[j]&&j<i)
        j++;
        for(k=i;k>j;k--)
            a[k]=a[k-1];
        a[k]=temp;
    }
}
----------------------------------------------------------
Approach:
   The approach is to follow the existing algorithm. Read algorithm on wikipedia. The basic idea is traverse the array form start, temporarily store value of current element and search for the place to the left of that element where the value fits. When you find the place, shift the elements after that position by one to make the void to place temporarily stored element.

No comments:

Post a Comment

feel free to ask your doubts... if any
you can post your doubts on
www.facebook.com/programsimply