Разница между этими двумя реализациями сортировки вставок

Я чувствую, что эти две реализации делают одно и то же, но было бы замечательно, если бы вы также дали мне знать, если они (с точки зрения производительности) делают одно и то же (например, с точки зрения количества выполненных инструкций). Благодарю.

<?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));

2

Решение

Нет, они не одинаковы. Функция sortOne является неправильная реализация из insertion sort,

Правильная реализация функции sortOne является:

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;
}

Учитывая производительность сейчас, они в основном имеют одинаковую производительность. Просто изменив цикл на цикл, вы не получите никакого изменения производительности.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]