Insertion Sort
Lesson 14 of 26 in Coddy's Arrays in C++ course.
Insertion sort is also a kind of sorting technique that also has time complexity O(n2) but is a little bit more optimized than bubble sort.
In this algorithm, the array is separated into two parts. One is sorted and the other is unsorted. we pick an element from an unsorted array and put it in a sorted array at its correct position.
we repeat the process until all the elements get sorted.
1. Suppose we have an array {8,4,1,5}. Consider the first element to be sorted and all others are unsorted. At first, the 0th element is considered sorted.
2. Create a temp variable and put the (i)th element (here it is 4). Compare temp with the currently sorted array which is 8 right now. As 4<8, shift the sorted array to the right until the 4 has its correct location. In this case, 8 have to be moved one time. Now the length of the sorted array has become 2.
3. We Repeat the process until the whole array got sorted.
for(int i=1;i<n;i++){ //start from first element as we consider 0th elemnt to be sorted
int temp=arr[i];
int j=i-1; //to check all elements from its left side
while(arr[j]>temp && j>=0){ //chane the elemnt till tempis less upto first element
arr[j+1]=arr[j]; //Push the element to right by one step
j--;
}
arr[j+1]=temp; //Put the temp in the corret position
}
To visualize insertion sort
Challenge
Given an array, sort it using insertion sort and find whether the updated array is in Arithmetic Progression or not? Return true if it is an AP else return false.
AP (Arithmetic Progression) is a sequence that has a constant difference between consecutive elements.
example. 10,20,30,40,...
Try it yourself
#include<iostream>
#include<vector>
using namespace std;
bool AP(vector<int>arr, int n){
//Code here
}