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.
Given an array of integers, the goal is to sort the array in ascending order using the Insertion Sort algorithm.
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.
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
- Start iterating through the array from the second element (index 1) to the last element.
- For each element, store its value in
jas the index of the previous element (i.e.,
i - 1).
jis non-negative and the element at index
jis greater than
currentElement, shift the element at index
jone position to the right.
currentElementin the correct position, which is
j + 1.
- Repeat steps 2-6 until the entire array is sorted.
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
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.