C Program to Sort an Array Using Insertion Sort


Sorting is a procedure in which the given elements are arranged in ascending or descending order. For example if the elements of an array are –

5, 11, 15, 8, 7, 54, 63, 44

After sorting these elements in ascending order, the elements would be –

5, 7, 8, 11, 15, 44, 54, 63

What is Insertion Sort is :

Insertion sort proceeds by inserting each element at the proper place in a sorted list. This is the same technique used by card players for arranging cards. When they receive a card, they place it in the appropriate place among the cards that they have already arranged.

We will consider our list to be divided into two parts – sorted and unsorted. Initially the sorted part contains only the first element of the list and unsorted part contains the rest of the elements. In each pass, the first element from the unsorted part is taken and inserted into the sorted part at appropriate place. If there are n elements in the list, then after n-1 passes the unsorted part disappears and our whole list becomes sorted. Let’s see the c program to sort an array using insertion sort.

C Program ►►

#include<stdio.h>
#include<conio.h>

void main()
{
   int size,arr[100],i,j,k;

   printf("Enter the Number of Elements : ");
   scanf("%d",&size);

   printf("\nEnter the elements of the Array : ");
   
   for(int i=0;i<size;i++) {
   printf("\nArray[%d] = ",i+1);
   scanf("%d",&arr[i]);
   }

   /* Insertion Sort */
   for(i=1; i<size ;i++)
   {

       k=arr[i]; 
    /*k is to inserted at proper place in sorted part*/
       
       for(j=i-1; j>=0 && k<arr[j] ;j--)
                  arr[j+1]=arr[j];
       
       arr[j+1]=k;
     
   } // end of outside for

   printf("\nSorted List is : \n");
   
   for(i=0;i<size;i++)
   printf("%d\t",arr[i]);
   
   getch();
   
}

Explanation ►► In each iteration of for loop, first element of the unsorted part is inserted into the sorted part. The element to be inserted (arr[i]) is stored in the variable k. In the inner for loop, the sorted part is scanned to find the exact location for the insertion of element arr[i]. The search starts from the end of the sorted part so variable j is initialized to i-1. The search stops when we either reach the beginning of the sorted part or we get an element less than k. Inside the inner for loop, the elements are moved right one position, and obviously these are elements which are greater than k, At the end k is inserted at its proper place.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s