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 Docusign

Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

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

Engage with a sea of insights in this enlightening article, highly esteemed within the encouraging DEV Community. Programmers of every skill level are invited to participate and enrich our shared knowledge.

A simple "thank you" can uplift someone's spirits. Express your appreciation in the comments section!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found this useful? A brief thank you to the author can mean a lot.

Okay