Table of Contents
About Insertion Sort
Insertion sort is a simple sorting that compares each element in the list to the elements that come before it and inserts it into its correct position in the sorted list. This process is repeated until all elements have been inserted into their correct positions and the list is sorted.
In insertion sort, we always start at the second index and compare values to the left (before).
Insertion Sort Algorithm
Explanation:
In insertion sort, we need to check all values, so we use two loops.
Firstly, we start the loop from the index 1.
To track the value of that index, we create a temporary variable
temp
in case we need to swap it.To compare to the left, we create a temporary variable
j
equal toi-1
.Since we do not know how many times we need to loop, we use a while loop.
If the value of temp
is less than the value on the left, we swap it and decrement j
to check the next value to the left.
We also need to stop once there is nothing to check. We add the condition j >= 0
to ensure that we stay within the bounds of the list.
5, we return the sorted array.
Function
function insertionSort(array $a): array
{
for ($i = 1; $i < count($a); $i++) {
$temp = $a[$i];
$j = $i - 1;
while ($temp < $a[$j] && $j >= 0) {
$a[$j + 1] = $a[$j];
$a[$j] = $temp;
$j -= 1;
}
}
return $a;
}
// $list = [5, 2, 8, 9, 1];
// insertionSort($list);
// [1, 2, 5, 8, 9]
Script
Try it on replit:
https://replit.com/@stafura/InsertionSort#main.php
Time Complexity
The time complexity of the insertion sort algorithm is O(n^2) in the worst-case scenario, where n is the number of elements in the list.
Despite its quadratic time complexity, insertion sort is a simple sorting algorithm that is well-suited to small lists or lists that are nearly sorted.
Top comments (0)