Second up in the line of sorting algorithms I'll run through is the
It's fairly different from the bubblesort algorithm in that bubblesort
will go through every element that you're trying to sort and compare it
with every other element (meaning, you're looking at about n * n
comparisons) while insertion sort will try to minimize the comparison by
ordering the elements better. Essentially, insertion sort takes one
element at a time and inserts it into another array in it's right place.
For each element, you only compare it with other elements until you find
one that's smaller than the element you're trying to insert.
In terms of steps, this means something like:
- Set a to value of element to insert.
- Set x to index of last element in sorted array.
- Compare a to sorted_array[x].
- If a is bigger than sorted_array[x], insert a at
- If a is smaller than sorted_array[x], shift value at x one place up
in the sorted array and decrement x.
- Repeat from 3 till done.
It's probably easier to figure out what's going on by looking at the
code - it's really rather simple.
class InsertionSort extends BaseSort
public function sortFunction()
$count = count($this->store);
$result = array();
$result = $this->store;
for ($i = 1; $i < $count; $i++)
$value = $this->store[$i];
$j = $i - 1;
while ($j >= 0)
if ($value < $result[$j])
$result[$j+1] = $result[$j];
$result[$j+1] = $value;
$this->store = $result;
Note: The code here makes use of the small test framework I created it
Sorting algorithms: quick
Quick run through: first, some housekeeping. An array for the result is
created, a count of the elements to sort is done and the first element
in the sorted array is inserted (it will always be the same element, so
better initialize it like this). Then the actual sorting takes place,
looping over every element and inserting it into the results array. This
is the more interesting part: the element to sort is compared to the top
of the results array and if it's smaller, the results array then gets
shifted. This keeps on going till a proper place is found for the
element to sort.
First, a test with 1.000 elements.
1000 elements to sort.
Sanity check. PHP native sort() algorithm took: 0.003070 seconds. Memory used: 64464 bytes
Running InsertionSort sort. Algorithm took: 0.326779 seconds. Memory used: 64344 bytes
At 1.000 elements, it's running in 3/5 the time of the bubblesort
10000 elements to sort.
Sanity check. PHP native sort() algorithm took: 0.039953 seconds. Memory used: 665928 bytes
Running InsertionSort sort. Algorithm took: 32.702462 seconds. Memory used: 665788 bytes
Scaling up by a factor of 10 results in 100 times longer execution time.
This is as expected: insertion sort should run in O(n^2^). The reason
for this is that while insertion sort minimizes the amount of
comparisons to be done compared with bubblesort, it has exactly the same
problem: for every element you add that needs to be sorted you're also
adding a large number of comparisons to do, even if only half as many as