Insertion Sort Program With Full Introduction

Insertion Sort
Introduction

Insertion sort is a simple sorting technique in which the sorted array is built one element at a time.
The main idea behind the insertion sort is that it inserts each item into its proper place in the final list.
This sorting technique is less efficient as compared to other more advanced algorithm such as quick and merge sort.
In this technique, the array of values to be sorted is divided into 2 sets. One that stores sorted values and the another one stores unsorted values.
The sorting algorithm will proceed until there are elements in the unsorted list.


Algorithm:

INSERTION_SORT(ARR,N)
Step 1: Repeat Steps 2 to 5 FOR K=1 to N-1
Step 2: SET TEMP=ARR[K]
Step 3: SET J=K-1
Step 4: Repeat WHILE TEMP<=ARR[J]
              SET ARR[J+1]=ARR[J]
              SET J=J-1
              [END OF INNER LOOP]
Step 5: SET ARR[J+1]=TEMP
Step 6: END


Program Of insertion SORT:

   #include <stdio.h>
   #include<conio.h> 
   main()
   {
   int n,arr[100],i,j,temp;
   printf("\n Enter number of elements \n");
   scanf("%d",&n);
   printf("\n Enter %d integers \n", n);
   for(i=0;i<n;i++)
   scanf("%d",&arr[i]);
   for(i=1;i<=n-1;i++)
   {
   j=i;
   while(j>0&&arr[j]<arr[j-1])
   {
   temp=arr[j];
   arr[j]=arr[j-1];
   arr[j-1]=temp;
   j--;
   }}
   printf("\n Sorted list in ascending order: \n");
   for(i=0;i<=n-1;i++) 
   printf("%d \n", arr[i]);
   getch();
   }


Output:

        Here is the output generated by the program-
        1st case:



      
        2nd case:


        
Discussion:

Insertion sort iterates, consuming one input element each repetition and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there. It repeats until no input elements remain.
Sorting is typically done in-place, by iterating up the array, growing the sorted list behind it. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position.

Post a Comment

0 Comments