Insertion Sort
Insertion sort
This image is just for analogy. This is not an actual representation of the algorithm.
Assuming that the entire array is divided into sorted and unsorted parts, each of the elements from the unsorted part is inserted into the correct position in the sorted part. Hence the name, Insertion sort.
Concept: Builds a sorted array one element at a time by inserting elements into their correct positions within the sorted portion of the array.
It has a time complexity of O(n^2), thus being slower than heapsort, merge sort and also shellsort. Insertion sort is well suited for sorting small data sets or for the insertion of new elements into a sorted sequence.
Idea :
- Let a0, …, an-1 be the sequence to be sorted.
- At the beginning and after each iteration of the algorithm the sequence consists of two parts:
- the first part a0, …, ai-1 is already sorted,
- the second part ai, …, an-1 is still unsorted (i element 0, …, n).
- In order to insert element ai into the sorted part, it is compared with ai-1, ai-2 etc.
- When an element aj with aj less or equal ai is found, ai is inserted behind it.
- If no such element is found, then ai is inserted at the beginning of the sequence.
- After inserting element ai, the length of the sorted part has increased by one.
- In the next iteration, ai+1 is inserted into the sorted part etc.
- While at the beginning the sorted part consists of element a0 only, at the end it consists of all elements a0, …, an-1.
Iterative approach
The part in blue color in this image is the sorted part. The inner for loop is for this sorted part.
The rest of it is the unsorted part.
At each step, compare the first element in the unsorted part with the element right before it (j - 1 or i - 1) and keep going until index 0.
Recursive approach
- step 1 : write a method that accepts the input array and an extra parameter that tells the method about the number of elements that should be sorted.
- step 2 : breaking condition