es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Cómo codificar un algoritmo de ordenamiento por mezcla en PHP.

28 Jul, 2023 Programación

He buscado mucho esto, pero hasta ahora no he encontrado nada. Tuve que hacer mi pregunta aquí.

En mi código actual obtengo el resultado dividiendo entre 2.

Datos de muestra: $example = [50, 20, 87]

Resultado esperado: 20, 50, 87

Lo que espero es cómo hacer esto dividiendo entre 3 en lugar de entre 2.

Aquí está el código:

function merge_sort(&$arrayToSort) {
    if (sizeof($arrayToSort) <= 1)
        return $arrayToSort;

    // dividimos nuestro arreglo de entrada en dos mitades
    // izquierda...
    $leftFrag = array_slice($arrayToSort, 0, (int)(count($arrayToSort)/2));
    // derecha...
    $rightFrag = array_slice($arrayToSort, (int)(count($arrayToSort)/2));

    // RECURSIÓN
    // dividimos las dos mitades en sus respectivas mitades...
    $leftFrag = merge_sort($leftFrag);
    $rightFrag = merge_sort($rightFrag);

    $returnArray = merge($leftFrag, $rightFrag);

    return $returnArray;
}

function merge(&$lF, &$rF) {
    $result = array();

    // mientras ambos arreglos tengan elementos
    while (count($lF) > 0 && count($rF) > 0) {
        if ($lF[0] <= $rF[0]) {
            array_push($result, array_shift($lF));
        } else {
            array_push($result, array_shift($rF));
        }
    }

    // no vi esto en el pseudocódigo,
    // pero se volvió necesario ya que uno de los arreglos
    // puede quedar vacío antes que el otro
    array_splice($result, count($result), 0, $lF);
    array_splice($result, count($result), 0, $rF);

    return $result;
}
Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para cambiar el código y ordenar dividiendo por 3 en lugar de por 2, debes realizar los siguientes cambios:

    1. Cambia la línea que divide el array en dos mitades para dividirlo en tres partes en su lugar:
    $leftFrag = array_slice($arrayToSort, 0, (int)(count($arrayToSort)/3));
$middleFrag = array_slice($arrayToSort, (int)(count($arrayToSort)/3), (int)(count($arrayToSort)/3));
$rightFrag = array_slice($arrayToSort, (int)(count($arrayToSort)/3) * 2);
    1. Cambia la línea de recursión para llamar a merge_sort() en los tres fragmentos en lugar de solo en los fragmentos izquierdo y derecho:
    $leftFrag = merge_sort($leftFrag);
$middleFrag = merge_sort($middleFrag);
$rightFrag = merge_sort($rightFrag);
    1. Cambia la función merge() para fusionar los tres fragmentos en lugar de dos:
    while (count($leftFrag) > 0 && count($middleFrag) > 0 && count($rightFrag) > 0) {
    if ($leftFrag[0] <= $middleFrag[0] && $leftFrag[0] <= $rightFrag[0]) {
        array_push($result, array_shift($leftFrag));
    }
    elseif ($middleFrag[0] <= $leftFrag[0] && $middleFrag[0] <= $rightFrag[0]) {
        array_push($result, array_shift($middleFrag));
    }
    else {
        array_push($result, array_shift($rightFrag));
    }
}
    1. Añade el código para manejar los casos en los que uno o dos fragmentos se vacían antes que los demás:
    if (count($leftFrag) == 0) {
    array_splice($result, count($result), 0, $middleFrag);
    array_splice($result, count($result), 0, $rightFrag);
}
elseif (count($middleFrag) == 0) {
    array_splice($result, count($result), 0, $leftFrag);
    array_splice($result, count($result), 0, $rightFrag);
}
elseif (count($rightFrag) == 0) {
    array_splice($result, count($result), 0, $leftFrag);
    array_splice($result, count($result), 0, $middleFrag);
}

    Después de realizar estos cambios, el código debería ordenar el array dividiendo por 3 en lugar de por 2, y el resultado esperado para los datos de muestra $example = [50,20,87] sería 20,50,87.

Comments are closed.