Insertion sort algorithm PHP implementation
This is a third blog post in my challenge to cover as many sorting algorithms as possible, implement them in PHP (without using any array functions) and then benchmark their performance with different inputs. Could be interesting.
Insertion sort is another common sorting algorithm. To explain how it works, try to imagine this. There’s a couple of cards on the table and you want to sort them in a correct order. You will pick a card from the table (based on any criteria, it doesn’t really matter, you can just pick the cards up randomly) and put it in your left hand at a correct position. To determine the correct position, you will compare it with every other card in your left hand starting from the right. This is a similar algorithm you might unconsciously use when playing cards with your friends.
Example:
-
<?php
-
-
$table = array(7, 3, 9, 6, 5, 1, 2, 0, 8, 4);
-
$leftHand = insertionSort($table);
-
var_dump($leftHand);
-
-
function insertionSort(array $table) {
-
$leftHand = array();
-
foreach ($table as $card) {
-
if (0 === count($leftHand)) {
-
$leftHand[] = $card;
-
} else {
-
$insertedCard = false;
-
$reindexedLeftHand = array();
-
for ($i = count($leftHand)-1; $i >= 0; –$i) {
-
if ($card >= $leftHand[$i]) {
-
for ($j = 0; $j <= $i; ++$j) {
-
$reindexedLeftHand[$j] = $leftHand[$j];
-
}
-
$reindexedLeftHand[] = $card;
-
for ($j = $i+1; $j < count($leftHand); ++$j) {
-
$reindexedLeftHand[$j+1] = $leftHand[$j];
-
}
-
$insertedCard = true;
-
break;
-
}
-
}
-
if (false === $insertedCard) {
-
$reindexedLeftHand[] = $card;
-
foreach ($leftHand as $cardInLeftHand) {
-
$reindexedLeftHand[] = $cardInLeftHand;
-
}
-
}
-
$leftHand = $reindexedLeftHand;
-
}
-
}
-
return $leftHand;
-
}
Will result in:
array(10) {
[0]=>
int(0)
[1]=>
int(1)
[2]=>
int(2)
[3]=>
int(3)
[4]=>
int(4)
[5]=>
int(5)
[6]=>
int(6)
[7]=>
int(7)
[8]=>
int(8)
[9]=>
int(9)
}
Trackbacks and Pingbacks