Optimizing bubble sort

[make-github-pseudonymous-again]

• 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]

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

[make-github-pseudonymous-again]

See https://quuxplusone.github.io/blog/2020/12/13/bubblesort-rocksort-shakersort/