Lecture 337:- Let's Code Insertion Sort

Here's a simple C++ implementation of the Insertion Sort algorithm:

cppCopy code

#include <iostream> #include <vector> using namespace std; void insertionSort(vector<int>& arr) {    int n = arr.size();    for (int i = 1; i < n; i++) {        int key = arr[i];        int j = i - 1;        // Move elements of arr[0..i-1] that are greater than key to one position ahead of their current position        while (j >= 0 && arr[j] > key) {            arr[j + 1] = arr[j];            j--;        }        arr[j + 1] = key; // Insert the key into its correct position    } } // Function to display the elements of the array void display(const vector<int>& arr) {    for (int val : arr)        cout << val << " ";    cout << endl; } int main() {    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};    cout << "Original Array: ";    display(arr);    insertionSort(arr);    cout << "Sorted Array: ";    display(arr);    return 0; }

In this implementation, the insertionSort function takes a vector of integers as input and sorts it using the Insertion Sort algorithm. The outer loop runs for n-1 passes, and the inner loop compares the key with elements to its left and shifts them to the right if needed to insert the key into its correct position. The display function is used to print the elements of the array before and after sorting.

When you run this code, it will display the original array and then the sorted array after applying the Insertion Sort algorithm.