PHP Insertion Sort Algorithm

Wiki

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)
}
0.00 avg. rating (0% score) - 0 votes