Optimizing bubble sort
make-github-pseudonymous-again opened this issue · 2 comments
make-github-pseudonymous-again commented
- https://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort
- move turtles at the beginning by recording the minimum element for each loop
make-github-pseudonymous-again commented
Example in PHP
function combinedBubbleSort(&$a) {
$n = count($a);
// bubble sorting
for ($j = 0; $j < ($n - 1); $j++) {
//echo "Iteration #".$j.EOL;
$flag = false;
$min = $j;
for ($i = $j; $i < ($n - $j - 1); $i++) {
//echo T.'#'.$i.T.'v'.$a[$i].EOL;
//echo "Comparation: ";
//printArray($a, array($i, $i + 1));
if ($a[$i] > $a[$i + 1]) {
//echo "Swap: ";
list($a[$i], $a[$i + 1]) = array($a[$i + 1], $a[$i]);
//printArray($a, array($i, $i + 1), 'blue');
if (!$flag) $flag = true;
}
if ($a[$i] < $a[$min]) $min = $i;
}
if (!$flag) break;
if ($min != $j) {
//echo "Swap: ";
list($a[$min], $a[$j]) = array($a[$j], $a[$min]);
//printArray($a, array($min, $j), 'yellow');
}
}
}