Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as QuickSort, MergeSort, or HeapSort, but it has the advantage of being simple to understand and implement. Insertion Sort works similarly to the way we sort playing cards in our hands. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand.

Problem Statement

Given an array of integers, the goal is to sort the array in ascending order using the Insertion Sort algorithm.

Example

Let's take the array [5, 1, 0, 9, 3, 1, 6, -3, 7, 1, -5, 12] as an example.

Idea to Solve

The basic idea behind Insertion Sort is to divide the input array into two parts: a sorted part and an unsorted part. Initially, the sorted part contains only the first element of the array, and the unsorted part contains the rest of the elements. The algorithm then iterates through the unsorted part and inserts each element into its correct position in the sorted part.

Pseudocode

function insertionSort(arr):
    for i from 1 to length(arr) - 1:
        currentElement = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > currentElement:
            arr[j + 1] = arr[j]
            j = j - 1
        arr[j + 1] = currentElement

Algorithm Explanation

1. Start iterating through the array from the second element (index 1) to the last element.
2. For each element, store its value in currentElement.
3. Initialize j as the index of the previous element (i.e., i - 1).
4. While j is non-negative and the element at index j is greater than currentElement, shift the element at index j one position to the right.
5. Decrement j by 1.
6. Place currentElement in the correct position, which is j + 1.
7. Repeat steps 2-6 until the entire array is sorted.

Code Solution

1) Insertion sort on array in java 2) Insertion sort on vector in c++ 3) Insertion sort on array in c++ 4) Insertion sort on array in c 5) Insertion sort on array in golang 6) Insertion sort on array in c# 7) Insertion sort on array in vb.net 8) Insertion sort on list in python 9) Insertion sort on array in scala 10) Insertion sort on array in swift 11) Insertion sort on array in kotlin 12) Insertion sort on array in ruby 13) Insertion sort on array in node js 14) Insertion sort on array in php

Time Complexity

The worst-case time complexity of the Insertion Sort algorithm is O(n^2), where n is the number of elements in the array. This occurs when the input array is in reverse order, and for each element, we need to shift all previous elements to the right. In the best-case scenario (already sorted array), the algorithm runs in O(n) time. The average-case time complexity is also O(n^2), making Insertion Sort less efficient compared to more advanced sorting algorithms for larger datasets.