QUICK SORT USING PHP AND TDD

July 24th, 2019 by Kevin Pimentel

The quick sort algorithms is learned by every Computer Science student in school. It's a simple sorting algorithm that involves selecting a pivot number and then arranging the initial array into one of two arrays, those that are smaller than the pivot, and those that are larger than the pivot.


return array_merge(quick_sort($left_array), [$pivot], quick_sort($right_array));

Then, using recursion, you continue to divide the array this way until there are no items left in the array, at which point you should have a sorted array. There's no real magic for selecting a pivot. For this implementation I'll be using the last item in the list. Generally, you don't want to select the first or last number in the array, because if the array is sorted, it will perform slower. Ideally, selecting a pivot from the middle of the array is the way to go.

Creating Our Test Class

To start we define a SortTest class where all of our tests are going to live. 


<?php

use PHPUnit\Framework\TestCase;
use App\Sort;

final class SortTest extends TestCase
{

}

Creating Our Quick Sort Test

I attended PHP[TEK] in Atlanta Georgia this year. The @grmpyprogrammer was there, teaching the courses on testing. The thing I found most interesting was the pattern for setting up tests. Although it's super simple, I had never heard of a testing pattern. I've been trying to incorporate more and more tests and I think that this pattern is a really clean way to setup your tests.

  1. Arrange
  2. Act
  3. Assert


He introduced us to the 3 A’s testing pattern. And it went something like this:

public function test_that_a_list_can_be_sorted_using_quick_sort()
{
     // Arrange
     $sort = new Sort();

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

     // Act
     $sorted = [2,3,4,4,5,24,32,43,54,56,57,424,563,676,5677];
     $quick_sorted = $sort->quick($list);

     // Assert
     $this->assertEquals($sorted, $quick_sorted);
}

Get Feedback

Of course, when we run this we get an undefined class error because we have yet to create our class Sort.php. TDD tells us what to do next, create the class Sort.php.


$ pu
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

E                                                                   1 / 1 (100%)

Time: 521 ms, Memory: 4.00 MB

There was 1 error:

1) SortTest::test_that_a_list_can_be_sorted_using_quick_sort
Error: Class 'App\Sort' not found

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

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

Creating Our Sort Class

Using TDD we know that we need to create the Sort.php class. If we continue to follow TDD, the next issue is the undefined method quick(). As we continue to receive more feedback from our tests, we know that the next step is to make the quick() method in our Sort class, which we referenced in our test. Our API continues to take form with the feedback from our TDD workflow.


<?php

namespace App;

class Sort
{
    public function quick(array $numbers) : array
    {
        return $numbers;
    }
}

Getting Our Test To Fail

We run the test once more but it fails because the lists are not equal. The first element in the array did match, so we have that going for us. Yay!


$ pu
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

F                                                                   1 / 1 (100%)

Time: 97 ms, Memory: 4.00 MB

There was 1 failure:

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

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

Implementing a Quick Sort Solution

Finally, it’s time to use our Computer Science and Data Structure skills. In order to make our test pass we are going to return a sorted array of the array input.


public function quick(array $numbers) : array
{
     if (count($numbers) <= 1) return $numbers;

     $pivot = $numbers[count($numbers) - 1];
     $left = [];
     $right = [];

     for ($i = 0; $i < count($numbers) - 1; $i++) {
         $method = ($numbers[$i] < $pivot)
                 ? 'left'
                 : 'right';

         array_push($$method, $numbers[$i]);
     }

     return array_merge($this->quick($left), [$pivot], $this->quick($right));
}

First thing we want to do is define our exit condition. Always, and whenever I write recursion, I make sure I can exit the method. It's the most important part of recursion.


if (count($numbers) <= 1) return $numbers;

Next, we want to be able to call the method as many times as needed. The obvious answer is to write a piece of code that calls itself.


return array_merge($this->quick($left), [$pivot], $this->quick($right));

Finally, the calculating portion of the method gets implemented. Before looping through the records, we iterate through the array $numbers. If an item in the array is less than the pivot, it goes into the left array. Otherwise, if it's greater (or equal), it goes into the right array.


In the end, we are left with a list of sorted numbers.


We run our test, and it passes!


$ pu
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

.                                                                   1 / 1 (100%)

Time: 87 ms, Memory: 4.00 MB

OK (1 test, 1 assertion)

Conclusion

The idea behind quick sort is that smaller arrays, or smaller problems, are easier to solve than large ones. We divide the array into smaller ones that are manageable and easy to sort, until we have a sorted list. Quick sort is a Divide and Conquer sorting technique that does have some useful real world applications.


GitHub


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.