Insertion Sort
Insertion sort is based on the idea that one element from the input elements is consumed in each iteration to find its correct position i.e, the position to which it belongs in a sorted array.
The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
This is done by shifting all the elements, which are larger than the current element, in the sorted array to one position ahead
Algorithm:
To sort an array of size n 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 it to the elements before. Move the greater elements one position up to make space for the swapped element.
Time Complexities:
Worst Case Complexity: O(n2)
If we want to sort in ascending order and the array is in descending order then, the worst case occurs.Best Case Complexity: O(n)
It occurs when the array is already sortedAverage Case Complexity: O(n2)
It occurs when the elements of the array are in jumbled order (neither ascending nor descending)
No comments