INSERTION SORT USING PHP AND TDD

July 25th, 2019 by Kevin Pimentel

The idea of insertion sorting is a simple one. You want to insert elements into an already sorted array. If you have a sorted array and you want to insert a new element, then you simply need to figure out where in the list to insert the new element.


How does it work?


There are really two things that need to happen:

  1. Retrieve an element from our array for a specific key.
  2. Insert a new element into the sorted array and determine where in the list to insert it.


The first thing we will do is assume that the first element in our array is sorted. There! Now we have a sorted array of one. That’s easy enough.


[5, 3, 2, 7, 4, 1]; // Start (sorted array[5])
[3, 5, 2, 7, 4, 1]; // insert 3 before 5 (sorted array[3,5])
[2, 3, 5, 7, 4, 1]; // insert 2 before 3 (sorted array[2,3,5])
[2, 3, 5, 7, 4, 1]; // insert 7 into the same spot (sorted array[2,3,5,7])
[2, 3, 4, 5, 7, 1]; // insert 4 before 5 (sorted array[2,3,4,5,7])
[1, 2, 3, 4, 5, 7]; // insert 1 before 2 (sorted array[1,2,3,4,5,7])

Let's Code It!

As always, I start by defining a test of what it is that we want to accomplish. We are going to want to call a method insertion that doesn’t yet exist in our Sort class. We will pass our unsorted array to insertion and expect for it to return a sorted list of items.

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

After defining our test we can run it and get feedback. Undefined method insertion error is the feedback that we receive from our TDD workflow. This tells us that we need to create the method insertion in our Sort class.

$ pf test_that_a_list_can_be_sorted_using_insertion_sort
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

E                                                                   1 / 1 (100%)

Time: 231 ms, Memory: 4.00 MB

There was 1 error:

1) SortTest::test_that_a_list_can_be_sorted_using_insertion_sort
Error: Call to undefined method App\Sort::insertion()

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

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

In the Sort class, we are going to want to accept an array and return a sorted array. 

 public function insertion(array $numbers) : array
 {

 }

If we run the test without returning an array, notice the feedback we receive. Return value of insertion() must be of the type array, none returned. Specifying the return type is a useful way of providing detailed feedback when someone interacts with out Sort class.

$ pf test_that_a_list_can_be_sorted_using_insertion_sort
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

E                                                                   1 / 1 (100%)

Time: 114 ms, Memory: 4.00 MB

There was 1 error:

1) SortTest::test_that_a_list_can_be_sorted_using_insertion_sort
TypeError: Return value of App\Sort::insertion() must be of the type array, none returned

C:\xampp\htdocs\sorting\src\Sort.php:29
C:\xampp\htdocs\sorting\tests\SortTest.php:23

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

All that is really left for us to do is return a sorted array using insertion sort.

public function insertion(array $numbers) : array
{
    for ($i = 1; $i < count($numbers); $i++) {
        for ($j = 0; $j < $i; $j++) {
            if ($numbers[$i] < $numbers[$j]) {
                $spliced = array_splice($numbers, $i, 1);
                array_splice($numbers, $j, 0, $spliced[0]);
            }
        }
    }


    return $numbers;
}

Insertion sort isn’t complex but it’s always been a little confusing for me to follow. 


In the first for loop we loop through the unsorted items. Since we are assuming the first element in our array to be sorted, we start the index at one.

for ($i = 1; $i < count($numbers); $i++) 

In the second for loop, we loop through every sorted element. We do this by looping through every available element before the current i iteration.

for ($j = 0; $j < $i; $j++)

Finally, our if statement checks if the last element in our sorted list is less than the current element in our j iteration. If this is the case, we remove the element and re-insert at the correct position. You are essentially performing an element swap.

if ($numbers[$i] < $numbers[$j]) {
    $spliced = array_splice($numbers, $i, 1);
    array_splice($numbers, $j, 0, $spliced[0]);
}

We run our test one last time and it passes: (I included a dump of the array)

$ pf test_that_a_list_can_be_sorted_using_insertion_sort
PHPUnit 8.2.5 by Sebastian Bergmann and contributors.

.                                                                   1 / 1 (100%)array(15) {
  [0]=>
  int(2)
  [1]=>
  int(3)
  [2]=>
  int(4)
  [3]=>
  int(4)
  [4]=>
  int(5)
  [5]=>
  int(24)
  [6]=>
  int(32)
  [7]=>
  int(43)
  [8]=>
  int(54)
  [9]=>
  int(56)
  [10]=>
  int(57)
  [11]=>
  int(424)
  [12]=>
  int(563)
  [13]=>
  int(676)
  [14]=>
  int(5677)
}


Time: 90 ms, Memory: 4.00 MB

OK (1 test, 1 assertion)

Conclusion


Insertion sorting can have some application with small already sorted lists. Outside of this scenario it's an inefficient sorting technique. A major disadvantage of insertion sorting is that if you want to insert a new element into the array it requires most elements be moved.


Insertion 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.