
Insertion Sort
This sorting algorithm works by repeatedly inserting elements into their correct position in an array.
Last updated
Was this helpful?
This sorting algorithm works by repeatedly inserting elements into their correct position in an array.
Last updated
Was this helpful?
Was this helpful?
Insertion sort is a simple sorting algorithm that works similarly to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct position in the sorted part.
Question statement:
https://www.codingninjas.com/studio/problems/insertion-sort_3155179
Notes:
https://drive.google.com/file/d/10zLQIWEn55nwhFOrHybqnxexf96AX1LE/view
void InsertionSort(int n, vector<int> &arr){
for(int i = 1; i < n; i++){
// for rounds 1 to n-1
//Here we assume 0 index value as sorted
int temp = arr[i];
int j = i-1;
for(; j >= 0; j--){
if(arr[j] > temp) // {1, 4, 2, 3}
// Shifting j index value forward by 1
arr[j+1] = arr[j]; // now array becomes {1, 4, 4, 3} 2 is already stored in temp
else
break;
}
swap(arr[j+1], temp);
}
}
Space Complexity:
constant O(1)
Time complexity:
O(n^2)
// 1st round - 1 Comp
// 2nd round - 2 Comp...
// (nth - 1) Round - (n-1) comp
Best case:
Already Sorted = {1, 2, 3, 4,} T.C = O(n)
// total comparisons (n-1)
Worst Case:
Reversed Array = {4, 3, 2, 1} T.C = O(n^2)