Insertion Sort

Insertion Sort:

To sort a list of numbers with insertion sort method, you can follow these steps:

1. Start with the first number in the list.
2. Compare it to the number before it (if there is one).
3. If the number is smaller than the previous one, keep comparing it to the numbers before until you find the right spot.
4. Move any larger numbers one position up to make space for the smaller number.
5. Repeat these steps for each number in the list until the whole list is sorted. Basically, you're checking each number and putting it in its correct place in the list by comparing it to the numbers that come before it. You keep doing this until the whole list is in the right order.

C++ Code

#include <bits/stdc++.h>
using namespace std;

void insertion_sort(int arr[], int n) {
    for (int i = 0; i <= n - 1; i++) {
        int j = i;
        while (j > 0 && arr[j - 1] > arr[j]) {
            int temp = arr[j - 1];
            arr[j - 1] = arr[j];
            arr[j] = temp;
            j--;
        }
    }

    cout << "After Using insertion sort: " << "\n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << "\n";
}

int main()
{
    int arr[] = {13, 46, 24, 52, 20, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Before Using insertion Sort: " << endl;
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;

    insertion_sort(arr, n);
    return 0;
}

Time Complexity: O(N^2)
Auxiliary Space: O(1)

Time Complexity Analysis of Insertion Sort
The worst-case time complexity - O(N^2)
The average case time complexity - O(N^2)
The time complexity of the best case - O(N).