The Spectrum of PHP by unknow

Author:unknow
Language: eng
Format: epub
Publisher: php[architect]
Published: 2023-09-15T00:00:00+00:00

Php Implementation

I started with the code for last month’s solution. The bubble sort is a case of the comb sort where the gap is always set to one. We’ll need a variable to define the starting gap and then narrow it as we loop through the array.

Listing 1 shows how to update the bubble sort to work like a comb sort. For starters, I chose a shrink factor of two. That makes the first gap half the size of our array. Shrink factors of less than two would compare elements that are farther away, while larger values compare items that are closer together (since this is a denominator when we calculate the gap.)

Wherever we had hardcoded 1 to compare elements or keep our loops within the bounds of our array, we can instead use $target.

Another thing to watch out for is letting the gap be set to zero. That happened to me when I used floor() to make the gap value an integer. If it falls to zero, the algorithm loops through the array, compares each element with itself, makes no swaps, and exits, leaving a partially sorted array.

Listing 1.

/** * We're assuming sequential integer keys * @param array<int, scalar> $list */ function comb_sort(array &$list): void { $max = count($list); $shrinkFactor = 2; $gap = ceil($max / $shrinkFactor); do { echo "
Gap: " . $gap; // stop two elements before max so we have two // elements to swap $swapped = false; for ($i = 0; $i < $max - $gap; $i++) { $target = $i + $gap; if ($list[$i] > $list[$target]) { $swapped = true; swap_elements($list, $i, $target); } } // reduce the gap again $gap = ceil($gap / $shrinkFactor); } while ($swapped); }

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.