Différence entre ces deux implémentations du tri par insertion

Question

J'ai l'impression que ces deux implémentations font la même chose, mais ce serait bien si vous pouviez aussi me dire si elles font la même chose (du point de vue des performances), par exemple en termes de nombre d'instructions exécutées. Je vous remercie.

<?php

$arr = array(10, 2, 3, 14, 16);

function sortOne($arr) {

    $instructionCount = 0;

    for ($i = 1; $i < count($arr); $i++) {
        $instructionCount++;
        for ($j = $i - 1; $j >= 0 && ($arr[$j] > $arr[$i]); $j--) {
            $instructionCount++;

            $tmp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $tmp;

        }
    }

    echo "\nTotal Instructions for Sort One: $instructionCount\n"; 

    return $arr;
}

function sortTwo($array) {

    $instructionCount = 0;

    for($j=1; $j < count($array); $j++){
        $instructionCount++;
        $temp = $array[$j];
        $i = $j;
        while(($i >= 1) && ($array[$i-1] > $temp)){
            $instructionCount++;
            $array[$i] = $array[$i-1];
            $i--;
        }
        $array[$i] = $temp;
    }

    echo "\nTotal Instructions for Sort Two: $instructionCount\n"; 

    return $array;
}

var_dump(sortOne($arr));

Answer 1

Non, ce ne sont pas les mêmes . La fonction sortOne est mauvaise mise en œuvre de insertion sort .

La mise en œuvre correcte de la fonction sortOne est :

for ($i = 1; $i < count($arr); $i++) {
    $instructionCount++;
    $temp = $arr[$i];
    for ($j = $i - 1; $j >= 0 && ($arr[$j] > $temp); $j--) {
        $instructionCount++;
        $arr[$j + 1] = $arr[$j];                
    }
    $arr[$j + 1] = temp;
}

Si l'on considère les performances actuelles, elles sont à peu près équivalentes. Le simple fait de remplacer la boucle for par une boucle while ne modifie en rien les performances.