De nuevo con otro code-kata ya estoy por aquí de nuevo. Se trata ahora de un algoritmo más sencillo que los anteriores. El Heapsort se apoya en montículos para su ordenamiento. El Quicksort hace un pivotaje algo complejo para hacer la división del vector en dos más simples. En este caso, el Mergesort, hace un ordenamiento más simple.
Mergesort aplica la estrategia de divide y vencerás para hacer el ordenamiento. Con esto, tenemos que un vector de números desordenado se divide en dos. Estos dos subvectores se ordenan por separado usando Mergesort recursivamente. Y al tenerlos ordenados, se fusionan en un vector final cogiendo elementos de uno u otro vector en orden creciente.
El caso base de la recursión es que tenemos uno o ningún elemento. Aquí ya tenemos el vector ordenado. En la fusión de dos vectores ya ordenados, simplemente inyectamos en el vector final el elemento menor de los dos vectores a fusionar.
El código
<?php
define('SIZE_OF_ARRAY', 30);
define('TRACE', true);
define('WAIT_TIME', 0);
$theArray = array();
for ($i = 0; $i < SIZE_OF_ARRAY; ++$i) {
$theArray[$i] = rand(0, 9);
}
$initialArray = $theArray;
$theArray = mergesort($theArray);
echo 'Initial array: '.implode('-', $initialArray).PHP_EOL;
echo 'Final array: '.implode('-', $theArray).PHP_EOL;
function mergesort($theArray)
{
printToScreen('>> mergesorting', $theArray, '');
if (count($theArray) <= 1) {
return $theArray;
} else {
$middlePos = count($theArray) / 2;
$U = mergesort(array_slice($theArray, 0, $middlePos));
$V = mergesort(array_slice($theArray, $middlePos, count($theArray) + 1 - $middlePos));
return Fussion($U, $V);
}
}
function Fussion($U, $V)
{
printToScreen('>> fussioning U', $U, '');
printToScreen('>> fussioning V', $V, '');
$i = $j = 0;
$finalArray = array();
while (count($U) > 0 and count($V) > 0) {
if ($U[0] < $V[0]) {
$finalArray[] = array_shift($U);
} else {
$finalArray[] = array_shift($V);
}
}
if (count($U) > 0) {
$finalArray = array_merge($finalArray, $U);
} else {
$finalArray = array_merge($finalArray, $V);
}
printToScreen('>> fussion', $finalArray, '');
return $finalArray;
}
function printToScreen($preStr, $theArray, $postStr)
{
if (TRACE) {
echo str_pad($preStr, 20, ' ');
foreach ($theArray as $item) {
echo str_pad($item, 3, ' ');
}
echo $postStr.PHP_EOL;
sleep(WAIT_TIME);
}
}
He marcado en negrita cómo se aplica la estrategia de divide y vencerás. Si lo grabas en un fichero .php y lo ejecutas deberías de ver algo parecido a esto:
>> mergesorting 0 9 3 8 0 2 9 0 4 7 2 9 7 3 6 7 0 8 8 1 0 7 2 1 4 9 8 1 4 5 >> mergesorting 0 9 3 8 0 2 9 0 4 7 2 9 7 3 6 >> mergesorting 0 9 3 8 0 2 9 >> mergesorting 0 9 3 >> mergesorting 0 >> mergesorting 9 3 >> mergesorting 9 >> mergesorting 3 >> fussioning U 9 >> fussioning V 3 >> fussion 3 9 >> fussioning U 0 >> fussioning V 3 9 >> fussion 0 3 9 >> mergesorting 8 0 2 9 >> mergesorting 8 0 >> mergesorting 8 >> mergesorting 0 >> fussioning U 8 >> fussioning V 0 >> fussion 0 8 >> mergesorting 2 9 >> mergesorting 2 >> mergesorting 9 >> fussioning U 2 >> fussioning V 9 >> fussion 2 9 >> fussioning U 0 8 >> fussioning V 2 9 >> fussion 0 2 8 9 >> fussioning U 0 3 9 >> fussioning V 0 2 8 9 >> fussion 0 0 2 3 8 9 9 >> mergesorting 0 4 7 2 9 7 3 6 >> mergesorting 0 4 7 2 >> mergesorting 0 4 >> mergesorting 0 >> mergesorting 4 >> fussioning U 0 >> fussioning V 4 >> fussion 0 4 >> mergesorting 7 2 >> mergesorting 7 >> mergesorting 2 >> fussioning U 7 >> fussioning V 2 >> fussion 2 7 >> fussioning U 0 4 >> fussioning V 2 7 >> fussion 0 2 4 7 >> mergesorting 9 7 3 6 >> mergesorting 9 7 >> mergesorting 9 >> mergesorting 7 >> fussioning U 9 >> fussioning V 7 >> fussion 7 9 >> mergesorting 3 6 >> mergesorting 3 >> mergesorting 6 >> fussioning U 3 >> fussioning V 6 >> fussion 3 6 >> fussioning U 7 9 >> fussioning V 3 6 >> fussion 3 6 7 9 >> fussioning U 0 2 4 7 >> fussioning V 3 6 7 9 >> fussion 0 2 3 4 6 7 7 9 >> fussioning U 0 0 2 3 8 9 9 >> fussioning V 0 2 3 4 6 7 7 9 >> fussion 0 0 0 2 2 3 3 4 6 7 7 8 9 9 9 >> mergesorting 7 0 8 8 1 0 7 2 1 4 9 8 1 4 5 >> mergesorting 7 0 8 8 1 0 7 >> mergesorting 7 0 8 >> mergesorting 7 >> mergesorting 0 8 >> mergesorting 0 >> mergesorting 8 >> fussioning U 0 >> fussioning V 8 >> fussion 0 8 >> fussioning U 7 >> fussioning V 0 8 >> fussion 0 7 8 >> mergesorting 8 1 0 7 >> mergesorting 8 1 >> mergesorting 8 >> mergesorting 1 >> fussioning U 8 >> fussioning V 1 >> fussion 1 8 >> mergesorting 0 7 >> mergesorting 0 >> mergesorting 7 >> fussioning U 0 >> fussioning V 7 >> fussion 0 7 >> fussioning U 1 8 >> fussioning V 0 7 >> fussion 0 1 7 8 >> fussioning U 0 7 8 >> fussioning V 0 1 7 8 >> fussion 0 0 1 7 7 8 8 >> mergesorting 2 1 4 9 8 1 4 5 >> mergesorting 2 1 4 9 >> mergesorting 2 1 >> mergesorting 2 >> mergesorting 1 >> fussioning U 2 >> fussioning V 1 >> fussion 1 2 >> mergesorting 4 9 >> mergesorting 4 >> mergesorting 9 >> fussioning U 4 >> fussioning V 9 >> fussion 4 9 >> fussioning U 1 2 >> fussioning V 4 9 >> fussion 1 2 4 9 >> mergesorting 8 1 4 5 >> mergesorting 8 1 >> mergesorting 8 >> mergesorting 1 >> fussioning U 8 >> fussioning V 1 >> fussion 1 8 >> mergesorting 4 5 >> mergesorting 4 >> mergesorting 5 >> fussioning U 4 >> fussioning V 5 >> fussion 4 5 >> fussioning U 1 8 >> fussioning V 4 5 >> fussion 1 4 5 8 >> fussioning U 1 2 4 9 >> fussioning V 1 4 5 8 >> fussion 1 1 2 4 4 5 8 9 >> fussioning U 0 0 1 7 7 8 8 >> fussioning V 1 1 2 4 4 5 8 9 >> fussion 0 0 1 1 1 2 4 4 5 7 7 8 8 8 9 >> fussioning U 0 0 0 2 2 3 3 4 6 7 7 8 9 9 9 >> fussioning V 0 0 1 1 1 2 4 4 5 7 7 8 8 8 9 >> fussion 0 0 0 0 0 1 1 1 2 2 2 3 3 4 4 4 5 6 7 7 7 7 8 8 8 8 9 9 9 9 Initial array: 0-9-3-8-0-2-9-0-4-7-2-9-7-3-6-7-0-8-8-1-0-7-2-1-4-9-8-1-4-5 Final array: 0-0-0-0-0-1-1-1-2-2-2-3-3-4-4-4-5-6-7-7-7-7-8-8-8-8-9-9-9-9
