What is Insertion Sort?
Data Structures and Algorithms play pivotal part in most of the applications. We see Google’s auto completion and correction in chrome search engine or Hadoop and spark engines which are used for big data or traffic routing in Internet, all these applications make use data structures and algorithms.
In this article, we are going to talk about one of the sorting algorithms called Insertion sort.
What are sorting algorithms?
A sorting algorithm is a method of re-organizing/arranging a given array of elements according to a comparison operator. Comparison operator can be highest-to-lowest value, alphabetical etc.
Why do we need sorting algorithms?
Sorting algorithms are used in arranging items by price or customer’s review in retail website like Amazon or it is also used in determining the order of site’s search on a search engine result page like Google chrome or safari.
There are many sorting algorithms such as quicksort, heapsort, merge sort etc., but today we will be concentration on Insertion sort.
The principle behind insertion sort is to remove an element from an unsorted input list and insert in the correct position in an already-sorted, but partial list that contains elements from the input list.
The input array is divided into 2 subgroups, sorted sub-array and unsorted sub-array. And it always considers the sorted sub-array and the next element which is to be sorted. Then the algorithm tries to insert the next element to the sorted sub-array at the appropriate position in ascending or descending order.
Let us see an example,
Consider the array shown below, which needs to be sorted in ascending order,
In the starting stage, it will be divided in to
The next element is 5, 5 will be inserted to sorted sub-array, resulting a sorted output array, the resulting array will be
Sorted sub-array is
Next element is 3,
When we place 3 in the appropriate position, the resulting array will be
In this array, the next element is 8, however 8 is already in correct position, i.e., the whole array is sorted in ascending order.
Thus we have sorted our input array using insertion sort!
To analyze sorting algorithms, we have some properties or observations. Will discuss them in the next section.
· Correctness
The algorithm has a property that, at each iteration, the array will consist of two, sub-arrays: the left sub-array is always sorted, so at each iteration the array will look like:
< (sorted array), current elements, (remaining elements)>
The current element will be inserted in the sorted sub-array in such a way that resulting array will also be sorted.
So, we can assume that by the time we insert the last element in the array, the whole array will be sorted.
· In-place sorting
A sorting algorithm is said to be in-place if it does not use any extra memory to sort the array. In insertion sort, at each iteration it removed one element from the input data, finds the location belongs within the sorted list and inserts it there. Since sorted list is also a part of input array, no extra array is required for sorting, hence Insertion sort is an in-place sorting array.
· Stability
A sorting algorithm is said to be stable if two equal numbers appear in the same order in the resulting array as they appear in the input array.
In insertion sort for ascending order, we will only swap the ordering of 2 elements if the item on the right is less than the item to its left. Therefore, the ordering of two equivalent items will always be preserved in insertion sort.
Let us consider a deck of cards to be sorted according number shown in the card, the two cards containing number 5 should be placed in the same order according to the input, then it is stable. Else, it is un-stable, which is depicted in the below image.
Even though 5 is there in two cards, one in red and other black color, since the input array contains red color card with 5 first followed by black color card with 5, red color card with 5 should come first in the output array. Then it is said to be stable.
· Online sorting
An algorithm is said to be offline if it requires the whole input data/array at the beginning for sorting, in contrast to this, online algorithm process its input element by element in a serial fashion, without having the entire input available in the beginning.
Insertion sort considers one element per iteration and produces a partial solution without considering the future elements, thus it is an online sorting algorithm.
Now that we have discussed about insertion sort in a detailed way, it is time for implementation. Pseudo code for insertion sort is given below
Try to implement the insertion sort in any programming language you prefer. I have implemented insertion sort in python for sorting in both ascending and descending order. Please find it here.
Happy Learning!!!
