Comb sort PHP implementation
After tackling the Shellsort, Comb sort is very similar. Shellsort was basically a generalisation of the Insertion sort, Comb sort is a generalisation of the Bubble sort. In the same way Shellsort was decreasing a gap between elements for subarrays been sent as input to the Insertion sort function, Comb sort is also decreasing the gap after every iteration and sending increasingly lengthy subarrays to the Bubble sort function.
According to Wikipedia, this algorithm works best with a shrink factor of around 1.3 (a little less than that but let’s keep this simple).
Here is my implementation:
-
<?php
-
-
define('SHRINK_FACTOR', 1.3);
-
-
$arr = array();
-
for ($i = 0; $i < 100; ++$i) {
-
$arr[] = $i;
-
}
-
shuffle($arr);
-
$sortedArr = combSort($arr);
-
var_dump($sortedArr);
-
-
function combSort(array $arr) {
-
$gap = floor(count($arr)/SHRINK_FACTOR);
-
while ($gap > 0) {
-
for ($i = 0; $i < count($arr)-$gap; ++$i) {
-
$arrWithGapsKeys = array();
-
$arrWithGaps = array();
-
$loop = true;
-
$j = $i;
-
while ($loop) {
-
if (isset($arr[$j])) {
-
$arrWithGapsKeys[] = (int)$j;
-
$arrWithGaps[] = $arr[$j];
-
$j += $gap;
-
} else {
-
$loop = false;
-
}
-
}
-
$arrWithGapsOrdered = bubbleSort($arrWithGaps);
-
foreach ($arrWithGapsKeys as $key) {
-
$arr[$key] = current($arrWithGapsOrdered);
-
next($arrWithGapsOrdered);
-
}
-
}
-
$gap = floor($gap/SHRINK_FACTOR);
-
}
-
return $arr;
-
}
-
-
function bubbleSort(array $arr) {
-
$sorted = false;
-
while (false === $sorted) {
-
$sorted = true;
-
for ($i = 0; $i < count($arr)-1; ++$i) {
-
$current = $arr[$i];
-
$next = $arr[$i+1];
-
if ($next < $current) {
-
$arr[$i] = $next;
-
$arr[$i+1] = $current;
-
$sorted = false;
-
}
-
}
-
}
-
return $arr;
-
}
Which will result in:
array(100) {
[0]=>
int(0)
[1]=>
int(1)
[2]=>
int(2)
[3]=>
int(3)
[4]=>
int(4)
[5]=>
int(5)
[6]=>
int(6)
[7]=>
int(7)
[8]=>
int(8)
[9]=>
int(9)
[10]=>
int(10)
[11]=>
int(11)
[12]=>
int(12)
[13]=>
int(13)
[14]=>
int(14)
[15]=>
int(15)
[16]=>
int(16)
[17]=>
int(17)
[18]=>
int(18)
[19]=>
int(19)
[20]=>
int(20)
[21]=>
int(21)
[22]=>
int(22)
[23]=>
int(23)
[24]=>
int(24)
[25]=>
int(25)
[26]=>
int(26)
[27]=>
int(27)
[28]=>
int(28)
[29]=>
int(29)
[30]=>
int(30)
[31]=>
int(31)
[32]=>
int(32)
[33]=>
int(33)
[34]=>
int(34)
[35]=>
int(35)
[36]=>
int(36)
[37]=>
int(37)
[38]=>
int(38)
[39]=>
int(39)
[40]=>
int(40)
[41]=>
int(41)
[42]=>
int(42)
[43]=>
int(43)
[44]=>
int(44)
[45]=>
int(45)
[46]=>
int(46)
[47]=>
int(47)
[48]=>
int(48)
[49]=>
int(49)
[50]=>
int(50)
[51]=>
int(51)
[52]=>
int(52)
[53]=>
int(53)
[54]=>
int(54)
[55]=>
int(55)
[56]=>
int(56)
[57]=>
int(57)
[58]=>
int(58)
[59]=>
int(59)
[60]=>
int(60)
[61]=>
int(61)
[62]=>
int(62)
[63]=>
int(63)
[64]=>
int(64)
[65]=>
int(65)
[66]=>
int(66)
[67]=>
int(67)
[68]=>
int(68)
[69]=>
int(69)
[70]=>
int(70)
[71]=>
int(71)
[72]=>
int(72)
[73]=>
int(73)
[74]=>
int(74)
[75]=>
int(75)
[76]=>
int(76)
[77]=>
int(77)
[78]=>
int(78)
[79]=>
int(79)
[80]=>
int(80)
[81]=>
int(81)
[82]=>
int(82)
[83]=>
int(83)
[84]=>
int(84)
[85]=>
int(85)
[86]=>
int(86)
[87]=>
int(87)
[88]=>
int(88)
[89]=>
int(89)
[90]=>
int(90)
[91]=>
int(91)
[92]=>
int(92)
[93]=>
int(93)
[94]=>
int(94)
[95]=>
int(95)
[96]=>
int(96)
[97]=>
int(97)
[98]=>
int(98)
[99]=>
int(99)
}
There are some variations of the Comb sort algorithm Combsort11 or Combsort with different end. I will show you how to implement them in the future.
Hi,
Your posts about sorting implementations inspired me to build my own sorting PHP extension, https://github.com/icex/exsort
I was working on a website that needed to handle and sort a large number of items(comma-separated lists of up to 100k integer mysql IDs) but the native sort function or mysql order by were really slow for real time performance.
With this PHP extension I went from 300-400ms to 20-40ms sorting time. It’s quite stable so far, we have it in production for two months now without issues.