DSA Tutorial


INSERTION SORT IN DSA



šŸ§© Insertion Sort in DSA

Insertion Sort is a simple sorting technique that builds the final sorted array one item at a time. It is much like sorting playing cards in your hands.

šŸƒ Think of cards: You pick one card at a time and insert it into its correct position in your already sorted hand.

šŸ”§ How It Works

  1. Start from the second element.
  2. Compare it with elements before it.
  3. Shift larger elements one position ahead.
  4. Insert the current element at its correct position.

šŸ“Œ Example

Given Array: [5, 2, 4, 6]

  • 2 is less than 5 ā†’ insert before ā†’ [2, 5, 4, 6]
  • 4 goes before 5 ā†’ [2, 4, 5, 6]
  • 6 stays ā†’ [2, 4, 5, 6]

šŸ’» C Code Example

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int a[] = {5, 2, 4, 6};
    int n = 4;
    insertionSort(a, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

ā±ļø Time Complexity:
Worst Case: O(nĀ²)
Best Case: O(n) (when array is already sorted)
Average Case: O(nĀ²)
šŸš€ Space: O(1) (In-place sorting)

šŸ’” Ideal for small datasets or arrays that are already nearly sorted.

šŸŒŸ Enjoyed Learning with Us?

Help others discover Technorank Learning by sharing your honest experience.
Your support inspires us to keep building!

Leave a Google Review