To gain a deeper understanding of insertion sort, lets first have a real-world approach to the word “sort”.
What is sorting?
In simple words, sorting means logically arranging data, that is, either in ascending or descending order.
But, where can we see sorting in real life? Although you come across sorting many times in your life, you may not have noticed it. For instance, let us consider an example of a student, David, in class 7.
He is assigned a task to arrange the mathematics test answer sheets in ascending order so that the student who scored the highest marks can be awarded. Let us assume that David completed the task and sorted the sheets in ascending order, and found that he was the one who scored the maximum marks. How can you justify this? This is because his sheet was at last in the stack(the bundle of the sheets), and since all the sheets were arranged in ascending order, so he was the one with the highest marks.
So he completed his task, but how did he do so? He used one of the many sorting techniques, for instance, say insertion sort.
Now that we are clear with the real-world examples of sorting, let us understand what is the use of sorting in computer science? There are plenty of uses.
For example:
- The contact list in your phone is sorted, which means you can easily access your desired contact from your phone since the data is arranged in that manner for you. In other words, “it is sorted”.
- While shopping on flip kart or amazon, you sort items based on your choice, that is, price low to high or high to low.
- The app docker on your phone is an easily relate-able example.
Now since we have a crystal clear idea about sorting in both perspectives, let us deep dive into Insertion Sort.
Insertion Sort
Insertion sort is the simple sorting algorithm that virtually splits the given array into sorted and unsorted parts, then the values from the unsorted parts are picked and placed at the correct position in the sorted part.
I hope you remember the task assigned to David. Let us assume David used the insertion sort technique to complete his task. Then he first chooses a number 1 as a pivot or origin, then starts with the other sheet and places the sheet with the marks and compares it with the marks on selected sheet number 1. If the sheet has fewer marks, he inserts it over and repeats the same process until he gets the sorted array.
Now speaking technically, the insertion sort follows the following algorithm to sort an array of size in ascending order:
1. Iterate from arr[1] to arr[n] over the array.
2. Compare the current element (key) to its predecessor.
3. If the key element is smaller than its predecessor, compare its elements before. Move the greater elements one position up to make space for the swapped element.
Example
Now let us apply the above algorithm for the task assignment to David and let the unsorted array of sheets be as follows:
He first compared the sheet on index 0 (number 1) with the marks on the sheet. As index 1 is lesser than marks on the sheet at index 0, he inserts it on the left side of the index 0. Now the new transformed array will look like this:
Note: The two elements at index 0 and index 1 have been swapped.
Now, he again compared the same selected sheet (number 1), which is now at index 1, with the marks on sheet at index 2 and finds that it is greater than the selected sheet (number 1) that is it is already sorted. Our array would be:
Now he again compares them. But this time, he compares the element at index 2 with the element at index 3, since the left part of index 2 is already sorted. He finds that the marks on index 3 are less than marks in the sheet at index 2, so he searches the right position for the sheet in the left (that is the sorted part) and finds the correct position at index 0. Now, the transformed array will be:
He again compares the element at index 3 with the element at index 4, and finds that marks on sheet at index 4 are less than on sheet at index 3. Thus, he finds the correct position for this element in the left (that is sorted part) and positioned it at index 1. Our sorted array will be:
So this is our sorted array. Now, can you tell how much David scored in his mathematics test? He scored 97 marks.
Now let’s apply this algorithm on our code in language C++:
// C++ program for insertion sort
#include <bits/stdc++.h>
using namespace std;
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
/* Driver code */
int main()
{
int arr[] = { 94,90,97,50,75 };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
return 0;
}
Output:
50 75 90 94 97
This brings us to the end of the blog on Insertion sort. We hope that you were able to learn more about the sorting algorithm.
Conclusion
With this, we have come to the end of this blog about insertion sort. We hope, by now, you might have gained a clear picture of what it is all about. Want to further your learning in the field? A well-structured PG in Software Engineering program might just be the answer.
