C++ Program to demonstrate Insertion Sort

Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array (or list) is built one entry at a time.

How it works:

  1. In insertion sort,elements are entered into the array(or list) 1-by-1.
  2. When the first element is entered, it is placed at the 1st position in the list(0th position in an array).
  3. When a new element is entered, it is compared to our already entered element and is decided whether to place before or after it in the list(array).
  4. Now when the third element is entered is entered, it is compared with the greater element of the 2 already existing elements. If smaller, then it is swapped. If not, then the array can be considered sorted.
    If swapped, then is compared with the smaller element of the 2 already existing elements and swapped again with it if it is even smaller.
  5. Similarly, all the the numbers to be placed in the list(array) are entered 1-by-1 and placed into the correct position right when they’re entered.

Example:

The following table shows the steps for sorting the sequence 5 7 0 3 4 2 6 1. On the left side the sorted part of the sequence is shown in red. For each iteration, the number of positions the inserted element has moved is shown in brackets. Altogether this amounts to 17 steps.

 

5 7 0 3 4 2 6 1 (0)
5 7 0 3 4 2 6 1 (0)
0 5 7 3 4 2 6 1 (2)
0 3 5 7 4 2 6 1 (2)
0 3 4 5 7 2 6 1 (2)
0 2 3 4 5 7 6 1 (4)
0 2 3 4 5 6 7 1 (1)
0 1 2 3 4 5 6 7 (6)

In our program, We have used:

  1. double arr[8]: A double datatype array of size 8 to store and sort any 8 numbers. Modify it to increase or decrease the number of elements to be entered and sorted (Also modify the conditions in the for loops.)
  2. int swaps: Integer variable to count the number of swaps performed.
  3. 1st for loop: To traverse through the array 8 times, accept 8 numbers and place them in their appropriate place (With the help of a nested while loop).
  4. int j=i: To start the array index for the while loop from i(location where the latest element has been placed).
  5. Nested while loop: This loop is nested in the above for loop. It compares and swaps the elements until the newly-inputted element reaches its appropriate place.
  6. swap(arg1,arg2): It is a predefined function and it swaps the data values of the 2 arguments passed to it.

The Program:

Tested in Visual C++/Visual Studio

The following two tabs change content below.

Lalit Mali

Lalit is a technology enthusiast, a programming lover and currently an Android fan.

One thought on “C++ Program to demonstrate Insertion Sort

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">