SELECTION SORT USING PHP AND TDD

July 26th, 2019 by Kevin Pimentel

One major advantage of selection sort is that if an element is in the right position, it will not be moved. When a swap occurs between two elements in an array, we can assume that at least one of the two elements has reached the final position. This means that selection sort performs at n-1 where n is the number of elements in our array. With sorting algorithms like this one, that perform swaps, n-1 is the most swaps that will be performed. 


How does it work?

Selection sort works by swapping the element with the largest value, with the element at the end of the unsorted list.

[5, 3, 2, 7, 4, 1]; // Start
[5, 3, 2, 1, 4, 7]; // Swap 7 and 1 (sorted array[7])
[4, 3, 2, 1, 5, 7]; // Swap 5 and 4 (sorted array[5,7])
[1, 3, 2, 4, 5, 7]; // Swap 4 and 1 (sorted array[4,5,7])
[1, 2, 3, 4, 5, 7]; // Swap 3 and 2 (sorted array[1,2,3,4,5,7])

Let's Code It!

I will step right into a test. Like our previous tests, we want to get a sorted list when we call the selection method.

public function test_that_a_list_can_be_sorted_using_selection_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->selection($list));
}

We run the test. The test yells at us. The test tells us we don't know how to define methods. We give up on programming? No. We have feedback and now we know what to do next.

$ pf test_that_a_list_can_be_sorted_using_selection_sort
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

E                                                                   1 / 1 (100%)

Time: 842 ms, Memory: 4.00 MB

There was 1 error:

1) SortTest::test_that_a_list_can_be_sorted_using_selection_sort
Error: Call to undefined method App\Sort::selection()

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

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

Here is my first implementation of the selection sort method. When we run the test we are going to get much more interesting feedback.

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

Of course, we didn't even attempt to sort the list, so it yells at us about how we didn't sort the list.

$ pf test_that_a_list_can_be_sorted_using_selection_sort
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

F                                                                   1 / 1 (100%)

Time: 165 ms, Memory: 4.00 MB

There was 1 failure:

1) SortTest::test_that_a_list_can_be_sorted_using_selection_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:32

...I guess we should sort it.


I know two things about selection sorting.

  1. We need to iterate over the array backwards in order to set the highest value at the end of the array.
  2. We need to swap the highest element in the array with the last unsorted element. (The current iteration)


What does any of that even mean?


We iterate backwards over the array because our $i value is going to track our last unsorted element. We then want to look through the rest of the array to see if there's anything higher than what we have at our $i position.


It's like telling someone "hey I have this number, and I'm not sure what it is, do you have a higher number I can trade you for?" If so, we swap!

public function selection(array $numbers) : array
{
    for ($i = count($numbers) - 1; $i > 0; $i--) {
        $this->swap($numbers, $this->max($numbers, $i), $i);
    }

    return $numbers;
}

Now if I run this I will get the next piece of feedback. Which is an undefined method swap. Unfortunately, just because I want to swap doesn't mean there is a swap method that already exists. We need to define it.

$ pf test_that_a_list_can_be_sorted_using_selection_sort
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

E                                                                   1 / 1 (100%)

Time: 414 ms, Memory: 4.00 MB

There was 1 error:

1) SortTest::test_that_a_list_can_be_sorted_using_selection_sort
Error: Call to undefined method App\Sort::swap()

C:\xampp\htdocs\sorting\src\Sort.php:44
C:\xampp\htdocs\sorting\tests\SortTest.php:32

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

I know I want to call this method swap, and I know it's going to accept three parameters.

$this->swap($numbers, $this->max($numbers, $i), $i);

The first parameter has to be the array. I also know that I am going to pass the array by reference. This will allow the array to be manipulated and for the changes to stick.


The next parameter is the max element, or the highest element in the unsorted list, that we want to place at the lowest level in the sorted list.


The last parameter is the current iteration. TDD helps us to define exactly what we want from our class ahead of time.

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

Just a good old-fashioned swap.


We run our test again, undefined method max.

$ pf test_that_a_list_can_be_sorted_using_selection_sort
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

E                                                                   1 / 1 (100%)

Time: 91 ms, Memory: 4.00 MB

There was 1 error:

1) SortTest::test_that_a_list_can_be_sorted_using_selection_sort
Error: Call to undefined function App\max()

C:\xampp\htdocs\sorting\src\Sort.php:44
C:\xampp\htdocs\sorting\tests\SortTest.php:32

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

Again, we forgot to define the max method and our PHPUnit test yells at us. PHPUnit never forgets.

$this->max($numbers, $i)

The max method needs to accept the array of elements and our current iteration.

private function max(array $numbers, int $high)
{
    $largest = 0;

    for ($i = 1; $i <= $high; $i++) {
        if ($numbers[$largest] < $numbers[$i]) {
            $largest = $i;
        }
    }

    return $largest;
}

In the max method we loop through the array starting at one. We don't need to start at zero because we'll be using the element at position zero as our largest element by default.


We compare every number in the array against the numbers array. Only when an element with a larger value then the element at index zero, or whatever element happens to be the largest at that moment, is the $largest variable updated. We continue looping until we have the largest index stored and then we return it.


We run our test one last time, and it passes!

$ pf test_that_a_list_can_be_sorted_using_selection_sort
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

.                                                                   1 / 1 (100%)

Time: 90 ms, Memory: 4.00 MB

OK (1 test, 1 assertion)

Conclusion

Because of how predictable this algorithm is, the two for loops iterate over completely predictable ranges, the worst and best cases are not going to differ by much. Since every swap yields at least one final position, the movement of elements is minimized, which makes it useful when dealing with larger data groups.


Sorting Repository

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.