Insertion Sort Algorithm Trace Steps and C++ Program

Today, we will discuss Insertion Sort Algorithm Trace Steps on Sample Data and C++ Program implementation of Insertion Sort. First of all, we will:

1. Define Insertion Sort
2. Explain the working of Insertion Sort 
3. Design an algorithm of Insertion Sort
4. Show trace steps of Insertion sort algorithm for sample data on paper.
5. Finally, write down the actual code of Insertion sort program in C++.

  What is Insertion Sort?

In Insertion sort, we have to insert elements in to correct position. First of all we find the correct position to insert for the key value under consideration. Secondly we will move other elements to make space for this new element (key value). Now we insert the new element at this space. Suppose there are the following elements in an array A to sort by insertion sort:

Working of Insertion Sort

1. Let first item be trivially sorted.
2. Now we consider first two items of list. Place second item on its correct location.
3. In Third pass we will consider first three items from list. Insert the 3rd item at its correct location among location1, location2 and location3.
4. In 4th pass, insert the 4th item at its correct location among location1, location2, location3 and location4.
5. And so on.

Algorithm of Insertion Sort

 Algorithm: INSERTION-SORT(array)
 This algorithm takes Array 'array' of size n numbers (array has index from 0 to n-1)as input. It sorts the given array in ascending order by INSERTION SORT method. i and j are integer variables used as index of array. temp is a temporary integer variable.
 1.   Repeat through step 6 for i ← 1 to n-1
 2.     temp  ← array[i]
 3.    Repeat through  step 5 while ( j > 0 && array[j-1] > temp)
 4.    array[j] ← array[j -1]
 5.    j ←   j - 1
 6.    array[j]← temp
 7.    End  

Insertion Algorithm Paper Tracing with data:a[0] ,a[1], a[2], a[3], a[4], a[5]
 5,       2,     4,      6,     1,     3
1. First of all we suppose that the first element 5 is its correct place or trivially sorted.

2. Now we consider second element 2. We have to insert 2 at its correct location from first two locations [0] and [1]. We will find its correct position from first two items 5 and 2.
3. Since 2 is less than 5, so the correct location of 2 is at array index[0].
4. We will move 5 from position [0] to [1].
5. Now we will place 2 at [0], so we have sorted first two items.

6. Now array = 2,5,4,6,1,3 Consider 3rd item which is 4. Now we find its correct location from first three locations. So 4 will be inserted at location [1] between 2 and 5.
7. We move 5 to position [2] and place 4 on position [1]
8. So first three items are sorted with array = 2,4,5,6,1,3

9. Now array = 2,4,5,6,1,3   consider 4th item 6 and place on its correct location among first four locations.
    We know that 6 is at its correct location which is 4th location and by index it is [3].

10. Now array is 2,4,5,6,1,3  consider 5th item which is 1. We know that its correct location between first
      five items is number one that is position [0] by index.
11. So we move 6 on [4]
           we move 5 on [3]
           we move 4 on [2]
           we move 2 on [1]
12. Now place 1 on position [0], so the array items a[0] to a[4] are sorted

13. Now array is 1,2,4,5,6,3   consider 6th item which is 3.
14. We know that 3 will be inserted at location [2] between item 2 and item 4.
15. We move 6 to location [5]
            move 5 to [4]
            move 4 to [3]
16. Now place 3 at location [2]
17. Hence the whole array has been sorted now     1,2,3,4,5,6
       
 You can check this all process in the following picture of insertion sort paper tracing.
   

Insertion Sort Algorithm Trace Steps and Program

Image: Trace steps : Insertion Sort Algorithm Trace Steps and Program

Easyway C++ : Insertion sort Algorithm trace steps and C++ Program

Program Insertion Sort in C++

/*
(c)EasyCppProgramming.Blogspot.Com
C++ is Simplified Here!
Target 1001 C++ Example Programs!
EasyCppProgramming.Blogspot.Com
*/

// Program To Input an array and sort
// the array by Insertion Sort Algorithm

#include<iostream>
#include<conio.h>

int main()
 {

   int n, array[100], i, j, t;

cout<<"\n/* Insertion sort Ascending order */\n";

  cout<<"Enter number of elements\n";
  cin>>n;

  cout<<"Enter "<<n<<" numbers\n";

  for (i = 0; i < n; i++)
    cin>>array[i];


for( i = 1;i < n; i++)
     {
     temp = array[i];
     for ( j = i; j > 0 && array[j-1] > temp; j--)
     array[j] = array[j-1];
     array[j] = temp;
     }

  cout<<"Sorted list in ascending order:\n";

  for (i = 0; i <= n - 1; i++)
    cout<<array[i]<<endl;

  getch();
  return 0;
}

Image: Sample Run of Program in Turbo C++ 3.0 - Insertion Sort Algorithm Trace Steps and Program

Easyway C++ : Insertion sort algorithm C++ Program Output Trace output

 Another Insertion Sorting Example for sorting data: 5,2,3,8,1

Figure: ample data trace steps: Insertion Sort Algorithm Trace Steps and Program

Insertion Sort Algorithm Trace Steps and Program - easyway C++ Program

So, we have completely discussed Insertion Sort Algorithm Trace Steps and Program, if you have any question please do not hesitate to ask question in comments section, thanks.

Further suggested Reading: Sorting Algorithms and Programs in C / C++

1.  Bubble Sort Algorithm and Program Logic in C Plus Plus

Read More

Bubble Sort Algorithm Trace Steps on Sample Data and C++ Program

Today, we will discuss Bubble Sort Algorithm and Program Logic in CPP ( C++ ) programming language. We will study:

1. Definition of Bubble Sort Algorithm
2. Trace steps for sample data or working of Bubble sorting algorithm
3. Algorithm of Bubble Sorting Method
4. Actual code of Bubble sort program in C++ programming language

 What is Bubble Sort?

Bubble sort is a sorting algorithm, in which we repeatedly pass through the whole array and swap the adjacent elements if they are not sorted.

Note that: In Bubble sort there will be maximum (n-1) passes to sort the given array. For example, if array size n = 5 then there will be (n-1) that is 4 passes.
Note that: In first pass there will be 4 comparisons like 5>4. In second pass there will be 3 comparisons. In third pass there will be two comparisons. And in last that is 4th pass there will be only one comparison.

Method of Bubble Sorting

• 1. Compare first two adjacent elements, if first is greater than second then swap them( if  sorting on ascending order)   
• 2. Repeat this comparison for second and third adjacent elements, then third and fourth elements and so on to second last and last elements. And swap the values where needed. This makes ONE PASS of Bubble Sort Algorithm.
• 3. Now again start with first and second element to compare and swap if first is greater than other. This time ignore last element. So you will compare adjacent elements from number 1 to second last element.
• 4. Similarly in third pass, you will reduce another comparison from end, and so on.
• 5. Keep repeating for one fewer element each time until there will be no pairs to compare. In Last Pass, there will be only one comparison of first and second element.

Bubble Sort Algorithm and Program Logic in CPP - on Sample Data

For example:

Let given un sorted array is:

5, 4, 3, 2, 1

In first pass:
5, 4, 3, 2, 1
Pass 1:

We will check if 5>4 then swap(5,4) so that array will become as follows
     4, 5, 3, 2, 1
    Next we will check if 5>3 then swap(5,3) so that array will become:
     4, 3, 5, 2, 1
    Next we will check if 5>2 then swap(5,2) so that array will become:
     4, 3, 2, 5, 1
    Next we will check that if 5>1 then swap(5,1) so that array will become:
    4, 3, 2, 1, 5
Note: You should note that in pass 1, the last element (5) is bubbled and placed to its correct location(sorted) in the given array.
Pass 2:

4, 3, 2, 1, 5
We will check if 4>3 then swap(4,3) which is true , so that array will become as follows:
     3, 4, 2, 1, 5
    Next we will check if 4>2 then swap(4,2) so that array will become:
     3, 2, 4, 1, 5
    Next we will check if 4>1 then swap(4,1) so that array will become:
     3, 2, 1, 4, 5
Note: You should note that in pass 2, the second last element (4) is bubbled and placed to its correct location(sorted) in the given array.

Pass 3:

3, 2, 1, 4, 5
We will check if 3>2 then swap(3,2) which is true , so that array will become as follows:
     2, 3, 1, 4, 5
    Next we will check if 3>1 then swap(3,1) so that array will become:
     2, 1, 3, 4, 5
Note: You should note that in pass 3, the third last element (3) is bubbled and placed to its correct location(sorted) in the given array.

Pass 4:
2, 1, 3, 4, 5
We will check if 2>1 then swap(2,1) which is true so the array becomes:
1, 2, 3, 4, 5

Which is the required sorted array.

  Bubble Sort Algorithm and Program Logic in CPP

Bubble Sort Algorithm

This algorithm will input values in array A of n size. Then sort the array by Bubble sort method and display the display the array. Suppose A be a linear array of n numbers. Temp is a temporary variable for swapping (interchanging) the position of the numbers in array as required according to the sorting order.
1. Input n numbers of an array A
    Initialise i=0 and repeat through 1b if (i<n)
    1a) Display Message " Enter a number="
    1b) Input A[i]
2. Initialise i= 0 and repeat through step 4 if (i< n)
3. Initialize j= 0 and repeat through step 4 if (j< n – i– 1)
4. If (A[j] > A[j + 1])
(a) Temp = A[j]
(b) A[j] = A[j + 1]
(c) A[j+ 1] = Temp
5. Display the sorted numbers of array A
    Initialise i=0 and repeat through 5a if (i<n)
    5a) Display A[i]
6. Exit.

Picture: Bubble Sort Algorithm and Program Logic in CPP

Bubble Sort Algorithm, Trace Steps on Sample data with C++ Program

Bubble Sort Program Code for Array of size s = 5 integer elements

Sample Run in Turbo C++ 3.0 IDE Bubble Sort Algorithm and Program Logic in CPP

Algorithm of Bubble Sort, Tracing Steps on Sample data with C++ Program

/*
(c)EasyCppProgramming.Blogspot.Com
C++ is Simplified Here!
Target 1001 C++ Example Programs!
EasyCppProgramming.Blogspot.Com
*/

// Program To Input an array and sort
// the array by Bubble Sort Algorithm

#include<iostream>
#include<conio.h>

int main()
 {

    int a[5], s=5, i, j, k, temp;
   clrscr();
   // input array
   cout<<"Enter 5 array elements to sort:\n";
   for(i=0;i<s;i++)
   cin>>a[i];
   // show un-sorted array
   cout<<"\n Un-Sorted array is =";
   for(i=0;i<s;i++)
   cout<<a[i]<<"    ";
   cout<<"\n------------------------------------";
   // sort array by bubble sort
    for(i=0;i<s-1;i++)
    {
    for(j=0;j<(s-1-i);j++)
            if(a[j]>a[j+1])
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
             }
cout<<"\nAfter Pass "<<(i+1)<<" elements are : ";
for (k = 0; k < s; k++)
cout<<a[k]<<"   ";
cout<<endl;
}/*End of outer for loop*/
    // show sorted array
   cout<<"\n ----------------------------------";
   cout<<"\nSorted Array is = ";

   for(i=0;i<s;i++)
   cout<<a[i]<<"    ";
   // wait for user to press any key
   getch();
   // end
   return 0;
 }

Now after studying Bubble Sort Algorithm and Program Logic in CPP, Read more on

Insertion Sort Algorithm Trace Steps and Program

Read More