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
- Start iterating through the array from the second element (index 1) to the last element.
- For each element, store its value in
currentElement
. - Initialize
j
as the index of the previous element (i.e.,i - 1
). - While
j
is non-negative and the element at indexj
is greater thancurrentElement
, shift the element at indexj
one position to the right. - Decrement
j
by 1. - Place
currentElement
in the correct position, which isj + 1
. - 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.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment