Insertion Sorting

 

Insertion sorting has also simplest algorithm in which the array is sorted by shifting the elements of the array one by one. The following are the characteristics of insertion sorting:

  1. The algorithm of insertion sorting is the simplest and can be implemented easily.
  2. Insertion sorting is mostly used when we have a smaller set of data because the algorithm for larger data set is not efficient.
  3. If some of the elements of the list are sorted already then the number of steps to sort the list are reduced hence we can say that insertion sorting is adaptive. The efficiency of the algorithm of insertion sorting is increased when we have a partially sorted list or array.
  4. Insertion sorting is more appropriate than selection sorting and bubble sorting.
  5. Insertion sorting also requires a single memory space for a temporary variable. Just like bubble sorting the space complexity of insertion sorting is less.
  6. The order of the elements is not changed when we use insertion sorting.

 

How Insertion Sorting Works?

Suppose we have an array that has elements 19, 12, 5, and 7. Consider the following figure to understand insertion sorting:

19 12 5 7

Now we take the first two elements of the array and we will compare them. The first two elements of the array are 19 and 12. As 12 is smaller than 19 therefore both of these elements will be swapped. Now the element 12 is at the index 0 and element 19 is at index 1 as follows:

12 19 5 7

Now the third element of the array is 5 as it is smaller than the first two elements of the array therefore it should be located at index 0. TO position this element of the array to index 0 we will shift the two elements that are 12 and 19 to the right side of the array. The new array will look like following:

5 12 19 7

Now the element 7 which is at index 3 of the array should not be there as it is smaller than 12 and 19. The right place for element 7 is between 5 and 12 that are in the index 1. To position the element 7 to index 1 we will shift the elements 12 and 19 to the right side and our new array will look like the following:

5 7 12 19

In this way we have a sorted array of elements.

 

Sorting using Insertion Sort Algorithm:

The following is the algorithm of sorting using insertion sort:

ALGORITHM:

int arr [5] = {4, 3, 6, 8, 3}

int x, y, n;

for (x = 1; x < 5; x++)

{

n = arr [x];

y = x – 1;

while (y > = 0; && n < arr [y])

{

arr [y + 1] = arr [y];

y –;

}

arr [y + 1] = n;

}

In the above algorithm of insertion sorting an array of 5 integers is declared. The variable n is used to store each element of the array. In each iteration of the loop, the variable n is stored with an element of the array. We have started from the second element of the array that is at the index arr [1].

After this a “while loop” is used which will be terminated when the value of the variable y becomes equal to zero or when an element is found that is greater than variable “n”. In the “while loop”, the variable n is inserted into the position of the array.

In the above algorithm n is given the value 3 which is the second element of the array and this element or value of “n” is compared with first element of the array which is 4. As 3 is smaller than 4, therefore, we shift both of these elements. Then there is the next element of the array that is 6. The element “6” is compared with the previous elements 4 and 3. As it is greater than 4 and 3 therefore, no shifting is performed. After 6, we have 8, it is compared with 4 and 3 and 6, and again no shifting will be performed. This process continues until the array is sorted.

 

Insertion Sorting in C++:

Consider the following example in C++ which implements insertion sorting:

CODE:

# include < stdlib. h>

# include < iostream. h>

using namespace std;

void insertionsorting (int a [], int len);

void printing (int arr [], int size);

int main () {

int array [6] = {2, 5, 7, 1, 6, 5};

insertionsorting (array, 6);

return 0;

}

void insertionsorting (int a [], int len) {

int x, y, temp;

for (x = 1; x < len; x ++) {

y = 1;

while (y > 0 && a [y – 1] > a [y]) {

temp = a [y];

a [y] = a [y – 1];

a [y – 1] = temp;

y –;

}

printing (a, 6)

}

void printing (int arr [], int size) {

cout << “Array after sorting using insertion sort”;

int y;

for (y = 0; y < size; y ++)

        for (y = 0; y < size; y ++)

              cout << “ ” << arr [y];

cout << endl;

}

In the above example, first we have declared two functions. The first function is used to sort the array using insertion sort technique and the second function is used to print the sorted array. In the main () function, an array of size 6 is declared. This array is passed to the insertionsorting () method with its size.

In the insertionsorting () method the array is sorted that is already explained. In this method we called the printing () method and passed the sorted array which is printed by using a nested loop.

 

Complexity Analysis of Insertion Sorting:

The following are the cases for time complexity of insertion sorting:

Worst case Time Complexity:

The worst case time complexity is o (n ^ 2)

Best case Time Complexity:

The best case time complexity is o (n)

Average Time Complexity:

The average case time complexity is o (n ^ 2)

Space Complexity:

The space complexity is o (1)