[PHP] Jak wykonać sortowanie przez wstawianie (algorym Insertion Sort)?

Chcesz wykorzystać do sortowania algorytm InsertionSort, czyli sortowanie przez wstawianie elementu.

To bardzo prosty algorytm, który nadaje się do sortowania niewielkich tablic. Polega na pobieraniu kolejnych elementów z części tablicy nieuporządkowanej i wstawianiu ich (stąd nazwa) do części tablicy już uporządkowanej.

Dwa skrypty to różne zapisy tego samego algorytmu:

<?

$t = array(7, 9, 1, 2, 6, 7, 3);

$n = count($t); // liczba elementów tablicy

for ($i=1; $i<$n;$i++) {

for ($j=$i;$j>0 && $t[$j]<$t[$j-1];$j--) {

if ($t[$j-1]>$t[$j]) list($t[$j-1],$t[$j]) = array($t[$j],$t[$j-1]);

}

}

for($i=0;$i<$n;$i++) echo $t[$i],", ";

// wynik: 1, 2, 3, 6, 7, 7, 9,

?>

Wymiana elementów tablicy została wykonana przy pomocy triku z list() i array(), bez potrzeby korzystania ze zmiennej tymczasowej.

A to wersja z pętlą while:

<?

$t = array(7, 9, 1, 2, 6, 7, 3);

$n = count($t); // liczba elementów tablicy

for ($i=1; $i<$n;$i++) {

$element=$t[$i];

$j=$i;

while($j>0 && $t[$j-1]>$element) {

$t[$j]=$t[$j-1];

$j--;

}

$t[$j]=$element;

}

for($i=0;$i<$n;$i++) echo $t[$i],", ";

// wynik: 1, 2, 3, 6, 7, 7, 9,

?>

Algorytm sprawdza się w tablicach, które są prawie posortowane, a więc gdzie niewiele elementów trzeba sortować.