SHELL SORT USING PHP AND TDD

July 27th, 2019 by Kevin Pimentel

One of the reasons for starting this blog is to document things as I learn them, for future me. Every year I like to go back to the basics and do a brush up on a few topics. I never understood Shell Sort before but I think I'm finally beginning to understand it.


How does it work?


First we need to pick a gap or an increment. Then, we are going to sort each sub-list increment. Next, we recombine the lists. Next, we decrease the gap, sort on the new increment. Finally, we do a list increment of one to sort the list.


[12, 5, 13, 3, 2, 7, 10, 4, 1, 9, 6, 8, 11, 14]; // Start

// Array gap of 5
[12, 7, 6]
[5, 10, 8]
[13, 4, 11]
[3, 1, 14]
[2, 9]

// Sort them for gap 5
[6, 7, 12]
[5, 8, 10]
[4, 11, 13]
[1, 3, 14]
[2, 9]

// Recombine them
[6, 5, 4, 1, 2, 7, 8, 11, 3, 9, 12, 10, 13, 14]

// Decrease gap - Array gap 3
[6, 1, 8, 9, 13]
[5, 2, 11, 12, 14]
[4, 7, 3, 10]

// Sort them
[1, 6, 8, 9, 13]
[2, 5, 11, 12, 14]
[3, 4, 7, 10]

// Recombine Them
[1, 2, 3, 6, 5, 4, 8, 11, 7, 9, 12, 10, 13, 14]

// Decrease gap - Array gap 1 / sort / recombine
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]


This one is hard to explain, I personally needed to write the example out and visualize it before I understood it.


Let's Code it!


I'll attempt to implement it, but first, a test.

public function test_that_a_list_can_be_sorted_using_shell_sort()
{
    $sort = new Sort();

    $list = [676,2,56,24,5,3,4,563,54,57,5677,43,32,4,424];

    $this->assertEquals([2,3,4,4,5,24,32,43,54,56,57,424,563,676,5677], $sort->shell($list));
}

Next, we know it's time to create the shell method.

$ pf test_that_a_list_can_be_sorted_using_shell_sort
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

E                                                                   1 / 1 (100%)

Time: 688 ms, Memory: 4.00 MB

There was 1 error:

1) SortTest::test_that_a_list_can_be_sorted_using_shell_sort
Error: Call to undefined method App\Sort::shell()

C:\xampp\htdocs\sorting\tests\SortTest.php:41

ERRORS!
Tests: 1, Assertions: 0, Errors: 1.

We create the shell method and return the $numbers array.

public function shell(array $numbers) : array
{
    return $numbers;
}

That fails because the list is not sorted.

$ pf test_that_a_list_can_be_sorted_using_shell_sort
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

F                                                                   1 / 1 (100%)

Time: 174 ms, Memory: 4.00 MB

There was 1 failure:

1) SortTest::test_that_a_list_can_be_sorted_using_shell_sort
Failed asserting that two arrays are equal.
--- Expected
+++ Actual
@@ @@
 Array (
-    0 => 2
-    1 => 3
-    2 => 4
-    3 => 4
+    0 => 676
+    1 => 2
+    2 => 56
+    3 => 24
     4 => 5
-    5 => 24
-    6 => 32
-    7 => 43
+    5 => 3
+    6 => 4
+    7 => 563
     8 => 54
-    9 => 56
-    10 => 57
-    11 => 424
-    12 => 563
-    13 => 676
-    14 => 5677
+    9 => 57
+    10 => 5677
+    11 => 43
+    12 => 32
+    13 => 4
+    14 => 424
 )

C:\xampp\htdocs\sorting\tests\SortTest.php:41

FAILURES!
Tests: 1, Assertions: 1, Failures: 1.

I had to consult my books and visit Wiki to see the algorithm written out.

 public function shell(array $numbers) : array
 {
     for ($gap = round(count($numbers) / 2); $gap > 0; ($gap = $gap / 2)) {
         for ($i = $gap; $i < count($numbers); $i++) {
             for ($j = $i - $gap; $j >= 0; $j -= $gap) {
                 if ($numbers[$j + $gap] >= $numbers[$j]) {
                     break;
                 }

                 $this->swap($numbers, $j+$gap, $j);
             }
         }
     }
     return $numbers;
 }

The first for loop manages the decreasing gaps. We start at n / 2 and decrease from there. As long as the gap is greater than 0 we continue to sort through our increments.


The second for loop steps through all of the gaps. The final for loop steps through the elements inside each gap.


We also get the chance to reuse this neat little method that does the swapping.

private function swap(array &$numbers, int $low, int $high)
{
    $temp = $numbers[$low];
    $numbers[$low] = $numbers[$high];
    $numbers[$high] = $temp;
}

We run our test and we pass!

$ pf test_that_a_list_can_be_sorted_using_shell_sort
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

.                                                                   1 / 1 (100%)

Time: 144 ms, Memory: 4.00 MB

OK (1 test, 1 assertion)


Shell Sort

Kevin Pimentel

There are two types of people in the world: those that code, and those that don’t. I said that! Quote me. My name is Kevin and I’m one of the ones that codes.