Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it is often used in practice for its simplicity and low overhead.

Here’s a basic description of how Insertion Sort works:

1. Start from the second element (assuming the first element is already sorted).
2. Compare the current element with its adjacent element.
3. If the current element is smaller, compare it with the previous elements in the sorted subarray and move them to the right until you find the correct position for the current element.
4. Repeat this process for each element in the array until the entire array is sorted.

Insertion Sort has a time complexity of O(n^2) in the worst case, but it can perform well for small datasets or partially sorted datasets. It is an in-place sorting algorithm, meaning it doesn’t require additional memory for sorting. It is also stable, preserving the relative order of equal elements in the sorted array.

Certainly! Here’s a simple implementation of the Insertion Sort algorithm in C++:

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    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 = j - 1;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    insertionSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

This C++ program defines a function insertionSort to perform the sorting and a helper function printArray to display the contents of an array. The main function initializes an array, prints the original array, calls the insertionSort function to sort it, and then prints the sorted array.

Conclusion of Insertion Sort

In conclusion, It is a simple and intuitive sorting algorithm that builds the sorted array incrementally by inserting elements into their correct positions. Here are some key points about Insertion Sort:

1. Time Complexity: The average and worst-case time complexity of Insertion Sort is O(n^2), where n is the number of elements in the array. This makes it less efficient than some other sorting algorithms for large datasets.
2. Adaptability: It is adaptive, meaning its performance is better when dealing with partially sorted arrays. If a significant portion of the array is already sorted, Insertion Sort can be more efficient compared to algorithms with a fixed time complexity.
3. Stability: It is a stable sorting algorithm. It preserves the relative order of equal elements, which can be important in certain applications.
4. In-Place Sorting: It is an in-place sorting algorithm, meaning it doesn’t require additional memory to perform the sorting.
5. Simple Implementation: It is relatively easy to implement and is a good choice for small datasets or situations where simplicity is more important than sorting speed.

In practice, while Insertion Sort is not as fast as some other sorting algorithms for large datasets, its simplicity and adaptability make it a reasonable choice for small datasets or situations where the array is already partially sorted. However, for larger datasets, more advanced algorithms like Quick Sort or Merge Sort are generally preferred.

For more know contact us+++ and do follow owners socially on insta @Sahil Rawat