Insertion Sort in C & C++ (Algorithm,concept,pseudocode and complexity)

Insertion Sort in C & C++

In this tutorial, I will explain to you the Concept, algorithm, Pseudocode, and complexity for insertion sort in C and C++ using program examples. The insertion sort inserts each element in the proper place. The strategy behind the insertion sort is similar to the process of sorting a pack of cards. You can take a card, move it to its location in sequence and move the remaining cards left or right as needed.

Concept :

Insertion sort is a sorting algorithm in which the elements are transferred one at a time to the right position. In other words, an insertion sort helps in building the final sorted list, one item at a time, with the movement of higher-ranked elements. An insertion sort has the benefits of simplicity and low overhead.

In an insertion sort, the first element in the array is considered as sorted, even if it is an unsorted array after which each element in the array is checked with the previous elements, resulting in a growing sorted output list. With each iteration, the sorting algorithm removes one element at a time and finds the appropriate location within the sorted array, and inserts it there. The iteration continues until the whole list is sorted.

There are many advantages associated with an insertion sort. It is simple to implement and is quite efficient for small sets of data, especially if it is substantially sorted.

How Insertion Sort Works ?

We take an unsorted array for our example.

Insertion sort compares the first two elements.

It finds that both 14 and 33 are already in ascending order. For now, 14 is in the sorted sub-list.

Insertion sort moves ahead and compares 33 with 27.

And finds that 33 is not in the correct position.

It swaps 33 with 27. It also checks with all the elements of the sorted sub-list. Here we see that the sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list remains sorted after swapping.

By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.

These values are not in sorted order.

So we swap them.

However, swapping makes 27 and 10 unsorted.

Hence, we swap them too.

Again we find 14 and 10 in an unsorted order.

We swap them again. By the end of the third iteration, we have a sorted sub-list of 4 items.

This process goes on until all the unsorted values are covered in a sorted sub-list. Now we shall see some programming aspects of insertion sort.

Algorithm

Now we have a bigger picture of how this sorting technique works, so we can derive simple steps by which we can achieve insertion sort.

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

Pseudocode

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
 
   for i = 1 to length(A) inclusive do:
 
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
  
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
  
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
 
end procedure

Program for Insertion Sort in C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include int main() {     int i,j,n,temp,a[30];     printf("Enter the number of elements:");     scanf("%d",&n);     printf("\nEnter the elements\n");     for(i=0;i<n;i++)     {         scanf("%d",&a[i]);     }     for(i=1;i<=n-1;i++)     {         temp=a[i];         j=i-1;         while((temp<a[j])&&(j>=0))         {             a[j+1]=a[j];    //moves element forward             j=j-1;         }         a[j+1]=temp;    //insert element in proper place     }     printf("\nSorted list is as follows\n");     for(i=0;i<n;i++)     {         printf("%d ",a[i]);     }     return 0; }

Program for Insertion Sort in C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include using namespace std; int main() {     int i,j,n,temp,a[30];     cout<<"Enter the number of elements:";     cin>>n;     cout<<"\nEnter the elements\n";     for(i=0;i<n;i++)     {         cin>>a[i];     }     for(i=1;i<=n-1;i++)     {         temp=a[i];         j=i-1;         while((temp<a[j])&&(j>=0))         {             a[j+1]=a[j];    //moves element forward             j=j-1;         }         a[j+1]=temp;    //insert element in proper place     }     cout<<"\nSorted list is as follows\n";     for(i=0;i<n;i++)     {         cout<<a[i]<<" ";     }     return 0; }

Complexity of Insertion Sort in C & C++

There is 1 comparison during pass 1 for a proper place. There are 2 comparisons during pass 2 for a proper place. There are 3 comparisons during pass 3 for the proper place, and so on accordingly.

F(n) = 1 + 2 + 3 + . . . . + (n-1) = n (n-1)/2 = O(n2)

Hence complexity for insertion sort programs in C and C++ is O(n2).

So this is it guys if you want us to write more on this topic or have any particular query regarding this post you can always comment or feel free to mail us at our official mail also follow us on Instagram and Facebook to receive Latest Updates first.

PEACE!!!