Insertion Sort

33 Comments / C++, Data Structure
Insertion Sort | Sahil Rawat | SKB Development

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

Related Posts

33 thoughts on “Insertion Sort”

  5. BlogMerk

    Hi i think that i saw you visited my web site thus i came to Return the favore I am attempting to find things to improve my web siteI suppose its ok to use some of your ideas

    Reply
  6. FeedNotes

    I loved as much as youll receive carried out right here The sketch is attractive your authored material stylish nonetheless you command get bought an nervousness over that you wish be delivering the following unwell unquestionably come more formerly again as exactly the same nearly a lot often inside case you shield this hike

    Reply
  7. TimesMerk

    hiI like your writing so much share we be in contact more approximately your article on AOL I need a specialist in this area to resolve my problem Maybe that is you Looking ahead to see you

    Reply
  8. BlogMerkk

    What i dont understood is in reality how youre now not really a lot more smartlyfavored than you might be now Youre very intelligent You understand therefore significantly in terms of this topic produced me personally believe it from a lot of numerous angles Its like women and men are not interested except it is one thing to accomplish with Woman gaga Your own stuffs outstanding Always care for it up

    Reply
  9. BusinesAfair

    I loved as much as you will receive carried out right here The sketch is attractive your authored material stylish nonetheless you command get got an impatience over that you wish be delivering the following unwell unquestionably come more formerly again since exactly the same nearly a lot often inside case you shield this hike

    Reply
  10. arediaa

    I do agree with all the ideas you have introduced on your post They are very convincing and will definitely work Still the posts are very short for newbies May just you please prolong them a little from subsequent time Thank you for the post

    Reply
  17. itsreleased

    My brother recommended I might like this web site He was totally right This post actually made my day You cannt imagine just how much time I had spent for this information Thanks

    Reply
  18. itsreleased

    I just could not depart your web site prior to suggesting that I really loved the usual info an individual supply in your visitors Is gonna be back regularly to check up on new posts

    Reply
  19. top888casino

    I loved as much as youll receive carried out right here The sketch is tasteful your authored material stylish nonetheless you command get bought an nervousness over that you wish be delivering the following unwell unquestionably come more formerly again since exactly the same nearly a lot often inside case you shield this hike

    Reply
  20. bestiptv-smarters

    I just could not depart your web site prior to suggesting that I really loved the usual info an individual supply in your visitors Is gonna be back regularly to check up on new posts

    Reply
  21. kmtfirm

    I am not sure where youre getting your info but good topic I needs to spend some time learning much more or understanding more Thanks for magnificent info I was looking for this information for my mission

    Reply

Leave a Comment

Your email address will not be published. Required fields are marked *