Lecture 334:- Insertion Sort

Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one item at a time. It is an in-place sorting algorithm, which means it rearranges the elements within the input array itself without requiring additional memory.

Algorithm:

1. Start from the second element (index 1) and consider it as a "key."
2. Compare the key with the element to its left (index -1) and move the left element one position right if it is greater than the key.
3. Repeat step 2 until the key is greater than or equal to the element to its left or reaches the beginning of the array.
4. Insert the key into the correct position after the loop completes for the current key.
5. Move to the next element (index 2) and repeat steps 2 to 4.
6. Continue this process until the last element is reached.

Here's the 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.