Shellsort PHP implementation
2012 June 19
Continuing my challenge, after implementing Bubble sort, Selection sort and Insertion sort, here comes 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)
}
2 Responses
leave one →
It is usually 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 edition.