DEV Community

Cover image for Insertion Sort
Ankit Kumar Meena
Ankit Kumar Meena

Posted on

2

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;
}
Enter fullscreen mode Exit fullscreen mode

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).

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay