Insertion Sort Algorithm in C++
Insertion Sort is an easy and efficient comparison-dependent sorting algorithm. It works by partitioning the input array into two parts: a sorted subarray and an unsorted subarray. First, the sorted subarray contains only the first element, and the unsorted subarray contains the remaining elements. The algorithm iterates through the unsorted subarray one element at a time and inserts each element into its correct position within the sorted subarray. It does this by repeatedly comparing the current element with the elements in the sorted sub-array and shifting more significant elements to the right to make space for the current element.
In each iteration of the insertion sort algorithm, an element is removed from the input list and inserted into the correct position in the already sorted list until no input element remains. This sorting is typically done in in-place. The resulting array after k iterations has the property where the first k + 1 entries are sorted.
The Key Steps of the Insertion Sort Algorithm:
1. Start with the first element of the array, considering it as the only element in the sorted sub-array.
2. Take the next element from the unsorted subarray and compare it with the elements in the sorted subarray. Shift elements to the right until you find the correct position for the current element in the sorted sub-array.
3. Repeat step 2 for all remaining elements in the unsorted subarray.
4. Continue this process until all elements are sorted.
Some Advantages of Insertion Sort Algorithm
- It is easy to understand and implement.
- It is efficient for small datasets or when the array is already partially sorted, as it performs fewer comparisons and swaps in such cases.
- It is an in-place sorting algorithm, meaning it doesn't require additional memory allocation.
However, Insertion Sort has a time complexity of O (n^2) in the worst case, making it less efficient for large datasets. In the best case, when the array is already sorted, it has a time complexity of O (n), and in the average case, it is also O (n^2). This makes it less suitable for sorting large datasets compared to more advanced sorting algorithms like Merge Sort or Quick Sort.
In summary, Insertion Sort is a straightforward sorting algorithm that builds a sorted subarray incrementally by inserting each element into its proper place within the sorted subarray. While it is not the most efficient choice for large datasets, it is suitable for small datasets and situations where the array is partially sorted.
Implementation of Insertion Sort Algorithm in C++:
#include<vector>
#include<iostream>
using namespace std;
void insertionSort(vector<int> &arr, int n){
for(int i = 1; i<n; i++){
int temp = arr[i];
int j = i-1;
while(j>=0){
if(arr[j]>temp){
arr[j+1] = arr[j];
}
else{
break;
}
j--;
}
arr[j+1] = temp;
}
}
int main(){
vector<int> arr = {4,5,1,2,7};
int n = arr.size();
insertionSort(arr,n);
for(int i = 0;i<n;i++){
cout<<arr[i]<<" ";
}
}
Output:
1 2 4 5 7
Performance Analysis of Insertion Sort Algorithm:
The insertion sort algorithm takes n-1 passes to sort a number of items. The iteration starts from position 1 and moves through position n-1, as these elements need to be inserted back into the sorted sub-lists.
- Best Case of Insertion Sort:
The best case of the insertion sort algorithm is O (n), i.e., when the input array is already sorted because only one comparison is required in each pass of the algorithm.
- Worst Case of Insertion Sort:
The worst case of the insertion sort algorithm is when the array is input in descending order, and we have to sort it in ascending order. For each I in the loop has to move all elements A [1], ……, A[n-1], which takes O(n-1) time.
T (n) = O (1) + O (2) + O (3) + ………… + O (n – 1)
T (n) = O (1 + 2 + 3 + 4 + …………… + n – 1) = O (n (n – 1)/2) = O (n2).
- Average Case Analysis:
In the case of the average case, the inner loop will insert A [i] in the middle of A [1], ………, A [n-1]. This takes O (i/2) time.
T(n) =∑_(i=1)^n▒〖O(n/2)=O(n^2 〗)
Conclusion:
Insertion sort is a simple and efficient comparison sort. Each iteration of the algorithm removes an element from the input array and inserts it into the sorted sub-list, which takes O (n) in the best case and O (n2) time in the worst case and average case.. A loop is run, and we detect the object frame by frame and mark the frame.