PHP Shellsort

Wiki

Shellsort, named after Donald Shell, it is basically a generalisation of simpler algorithms like Bubble sort or Insertion sort. It starts with far apart elements. The gap between elements is then decreased after every iteration.

That means we start with small subarrays and then with every iteration the subarrays are getting bigger as we are decreasing the gap between elements. I chose to start with a gap equal to half of the array length rounded down. After every iteration I divide the gap by two and round down again until zero is reached.

Example

<?php
 
$arr = array();
for ($i = 0; $i < 100; ++$i) {
    $arr[] = $i;
}
shuffle($arr);
$sortedArr = shellSort($arr);
var_dump($sortedArr);
 
function shellSort(array $arr) {
    $gap = floor(count($arr)/2);
    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 = insertionSort($arrWithGaps);
            foreach ($arrWithGapsKeys as $key) {
                $arr[$key] = current($arrWithGapsOrdered);
                next($arrWithGapsOrdered);
            }
        }
        $gap = floor($gap/2);
    }
    return $arr;
}
 
function insertionSort(array $table) {
    $leftHand = array();
    foreach ($table as $card) {
        if (0 === count($leftHand)) {
            $leftHand[] = $card;
        } else {
            $insertedCard = false;
            $reindexedLeftHand = array();
            for ($i = count($leftHand)-1; $i >= 0; --$i) {
                if ($card >= $leftHand[$i]) {
                    for ($j = 0; $j <= $i; ++$j) {
                        $reindexedLeftHand[$j] = $leftHand[$j];
                    }
                    $reindexedLeftHand[] = $card;
                    for ($j = $i+1; $j < count($leftHand); ++$j) {
                        $reindexedLeftHand[$j+1] = $leftHand[$j];
                    }
                    $insertedCard = true;
                    break;
                }
            }
            if (false === $insertedCard) {
                $reindexedLeftHand[] = $card;
                foreach ($leftHand as $cardInLeftHand) {
                    $reindexedLeftHand[] = $cardInLeftHand;
                }
            }
            $leftHand = $reindexedLeftHand;
        }
    }
    return $leftHand;
}

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)
}
0.00 avg. rating (0% score) - 0 votes