Sorting Algorithm: Insertion Sort

Sorting Algorithms

• Various sorting algorithms which we will study in this chapter are ‒

1. Insertion sort

2. Merge sort

3. Quick sort

4. Heap sort

 

Sorting Algorithm: Insertion Sort

Insertion sort builds the final sorted list one element at a time.

• It takes each element from the input and inserts it into its correct position in the already‒sorted part of the list.

• In this method the elements are inserted at their appropriate place. Hence is the bere name insertion sort. Let us understand this method with the help of some example –

For example

Consider a list of elements as,

The process starts with first element.

Algorithm

1. Store the list of unsorted elements in an array

2. Set a marker for the sorted zone after the first number in the list

3. Repeat steps 4 through 6 unit the unsorted zone is empty

4. Select the first unsorted number

5. Swap this number to the left unit it arrives at the correct sorted position

6. Advance the marker to the right one position

7. Stop

 

Example : 1

Sort the sequence 4, 7, 2, 0, ‒8, 5 using insertion sort.

Solution :

Consider that the elements are stored in an array as follows:

 

Analysis

• When an array of elements is almost sorted then it is best case complexity. The best case time complexity of insertion sort is O(n).

• If an array is randomly distributed then it results in average case time complexity which is O(n ²).

• If the list of elements is arranged in descending order and if we want to sort the elements in ascending order then it results in worst case time complexity which is O(n²).

 

Advantages of insertion sort

1. Simple to implement.

2. This method is efficient when we want to sort small number of elements. And this method has excellent performance on almost sorted list of elements.

3. More efficient than most other simple O(n²) algorithms such as selection sort or bubble sort.

4. This is a stable (does not change the relative order of equal elements).

5. It is called in‒place sorting algorithm (only requires a constant amount O(1) of extra memory space). The in‒place sorting algorithm is an algorithm in which the input is overwritten by output and to execute the sorting method it does not require any more additional space.

 

• Let us now see the implementation of this method using C++.

/**************************************************************

Implementation of insertion sort

***************************************************************/

#include<iostream>

using namespace std;

class Sort

{

private:

    int A[10];

    int n;

public:

    void get _data();

    void Insert _sort();

    void display();

};

void Sort::Insert _sort().

{

int i,j,temp;

for(i=1;i<=n‒1;i++)

{

    temp‒A[i];

    j=i‒1;

    while((j>=0)&&(A[j]>temp))

    {

        A[i+1]=A[i];

        j=j‒1;

    }

    A[j+1]=temp;

}

}

void Sort::get_data()

}

cout<<"\n How many elements are there?";

cin>>n;

cout<<"\n Enter the elements\n";

for(int i=0;i<n;i++)

cin>>A[i];

}

void Sort::display()

{

    cout<<"\n The sorted list of elements is...\n";

    for(int i=0;i<n;i++)

        cout<<"\n     "<<A[i];

}

void main()

{

    Sort obj;

    clrscr();

    cout<<"\n\t\t Insertion Sort";

    obj.get_data();

    obj.Insert_sort();

    obj.display();

    getch();

}

Output

Insertion Sort

How many elements are there?7

Enter the elements

3

1

2

5

4

7

6

The sorted list of elements is...

1

2

3

4

5

6

7

 

Logic explanation

• For understanding the logic of above C++ program consider a list of unsorted elements as,

• Then the control moves to while loop. As j >= 0 and A[j] > temp is True, the while loop will be executed.

• Now since j >= 0 is false, control comes out of while loop.

• Then list becomes,

• Thus we have scanned the entire list and inserted the elements at corresponding locations. Thus we get the sorted list by insertion sort.

 

Review Question

1. Explain insertion sort with its time complexity.