DEV Community

Harsh Bhardwaj
Harsh Bhardwaj

Posted on

1

Insertion Sort

Straight Insertion Sort

algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists. However, it has the advantage of being simple and adaptable, making it efficient for small datasets.

T(C) = O(n^2) where as Space Taken is constant as it sorts in place.

Steps:

  1. Start with the second element (assuming the first element is sorted).
  2. Compare the current element with the elements in the sorted portion and shift all the elements greater than the current element to the right.
  3. Insert the current element into its correct position.
  4. Repeat the process for all elements in the array.

Code:

#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;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Enter fullscreen mode Exit fullscreen mode

Special Points

  1. Simplicity: Easy to implement and understand.
  2. Stable: Maintains the relative order of equal elements.
  3. In-Place Sorting: Does not require extra memory.
  4. Efficient for Small Datasets: Performs well for small or nearly sorted datasets.

Image description

SHell Sort

It sorts elements at a specific interval first and gradually reduces the interval until it performs a final pass using insertion sort.

Passes:

Initial Array: [12, 34, 54, 2, 3]

Pass 1: Gap = 2
Elements Compared: [12, 54], [34, 2], [54, 3]

Reordering:
Compare and swap 12 and 54: [12, 34, 54, 2, 3]
Compare and swap 34 and 2: [12, 2, 54, 34, 3]
Compare and swap 54 and 3: [12, 2, 3, 34, 54]

Array after Pass 1: [12, 2, 3, 34, 54]

Pass 2: Gap = 1

Reordering:
Compare and swap 12 and 2: [2, 12, 3, 34, 54]
Compare and swap 12 and 3: [2, 3, 12, 34, 54]
No further swaps needed as array is already sorted

Array after Pass 2: [2, 3, 12, 34, 54]

#include <iostream>
using namespace std;

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    shellSort(arr, n);
    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Enter fullscreen mode Exit fullscreen mode

Performs Better than Insertion Sort // Unstable

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more