Insertion Sort in data structure | Algorithm with Examples

Insertion sort in data structure | insertion sort algorithm in data structure | insertion sort example | insertion sort javascript

Insertion Sort is one of the simplest sorting techniques which you might have used in your daily lives while arranging a deck of cards.

Since we insert one element at a time in its correct position, hence its name “Insertion Sort”.

✔️ Solution Approach

Outer For loop: This loop will start from array Index 1 to the last Index. Why from Index 1? Because a single element is itself in sorted order.

Inner While Loop: This while loop will run for all Elements below I’th Index to Index 0 and until the J’th element is less than the I’th element. If the current element (I’th) is less than any previous element stop comparing at that point.

If the Current I’th element < J’th element then move the Jth element to one position next that is J + 1.

Store the I’th element to a variable like currentElement and when the loop ends then place it in its correct position.

💻 Without any further explanation Start coding.

function insertionSort(A) {
    // Single element is itself sorted. So A[0] is in sorted order.
    for (let i = 1; i < A.length; i++) {
        const currElement = A[i];
        let j = i - 1; // start from left to currElement
        while (j >= 0 && A[j] > currElement) { // if true, do shift
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = element;
    }
    return A;
}

▶️ Understand Above Algorithm

Sort Below array step by step.

Arr  = [10, 9, 1, 3]

Single element is itself sorted. If we take element 10 only then it is already
in sorted order because no any other elements to compare in it's Left side.

> I start from 1 to 3 (3 is last index)
> Current Element is 9
> Now Compare 9 with all previous elements. If current element is less than
 the any previous element stop comparing at that point.

> I  is 1 so J will start from 0

> Compare 9 to 10 => 9 < 10 => So We need to shift 10 at one place to its next.

Arr  = [10, 10, 1, 3]

> Now J = -1 and I = 1

> No any further elements remained to compare so stop comparison.

> We have to place current element 9 to its correct position and that is J + 1.

Arr  = [9, 10, 1, 3]

> I = 2 that is A[2] = 1

> Current element is 1.

> J will go from 1 to 0 because I is 2.

> A[2] < A[1] => YES => So Shift Jth element means 10 to one position next.

Arr  = [9, 10, 10, 3]

> Now J = 0

> Compare 1 to 9 => 1 < 9 => YES => Again move 9 to one position next.

Arr  = [9, 9, 10, 3]

> Now J = -1. Stop comparing.

> Place current element to J + 1 position.

Arr  = [1, 9, 10, 3]

> Now I = 3 => A[3] = 3

> Current Element = 3

> J will start from 2 to 0 because i is 3.

> 3 < 10 => YES => Shift 10 to next.

> Arr  = [1, 9, 10, 10]

> J is now 1.

> 3 < 9 => YES => Shift 9 to next.

> Arr  = [1, 9, 9, 10]

> J is now 0.

> Compare 1 to 3 and 3 < 1 => FALSE => stop comparing.

> At this time J is 0 and Now its time to place current element to
 correct position and that will be J + 1.

> Arr  = [1, 3, 9, 10]

> Finished Algo.

insertionSort([5, 2, 10, 9, 1, 3])

output => [1, 2, 3, 5, 9, 10]

Insertion sort in data structure | insertion sort algorithm in data structure | insertion sort example | insertion sort javascript

💡Insertion Sort Time Complexity

We can see that two operations are performed by Insertion sort. First It scans all items of the array and second, it shifts items to other places when they are out of order.
So total time complexity is O(n^2)

We are not using any extra space here so Space Complexity is O(1)

💡Real-world Examples of Insertion Sort

Sorting a hand of playing cards.
Sorting names in a phone book.

💡Use Cases of Insertion Sort

Implementing autocomplete features in text editors.
Sorting online transaction records in a financial application.

FAQs

Q: Is Insertion Sort stable?
A: Yes, Insertion Sort is a stable sorting algorithm, meaning that it maintains the relative order of equal elements.
Q: Can Insertion Sort be used for sorting linked lists?
A: Yes, Insertion Sort can be applied to sort linked lists efficiently.
Q: How does Insertion Sort perform compared to Bubble Sort?
A: Insertion Sort usually performs better than Bubble Sort, especially for large datasets.
Q: What are some alternative sorting algorithms to Insertion Sort?
A: Some alternatives include Merge Sort, Quick Sort, and Heap Sort.
Q: When should I use Insertion Sort in my programs?
A: You should use Insertion Sort when dealing with small datasets or when the list is already partially sorted.

Quick Sort Algorithm with example | Step-by-Step Guide

Selection Sort Algorithm & K’th Largest Element in Array

Insertion sort step-by-step | insertion sort algorithm in data structure | insertion sort example | insertion sort javascript

JS Mount

Learn More