Selection Sort Exercise - Control Flow - PHP

Objective

Given an array of numbers, sort it using the selection sort algorithm.

Description

Sorting is one of the most useful aspects of studying programming and computer algorithms. At its core, it's just to rearrange the existing elements of an array such that they line up in ascending (or descending) order.

That is, the smallest element comes first, then the second smallest element, then the third smallest element, and so on and so forth.

Now there are various kinds of sorting algorithms. Each attacks the problem of sorting in a different way. One particularly simple and intuitive sorting algorithm is selection sort.

It proceeds as follows:

The minimum number is found in the entire array and then swapped with the first element.
Next, the second minimum is found, by iterating over the array starting at index 1 and going up to the very end of the array, and then swapped with the second element.
Next, the third minimum is found, by iterating over the array starting at index 2 and again going up to the very end of the array, and then swapped with the third element.
This goes on until the array to go over has effectively just one element to consider.

In other words, we successively find minimum values and swap them with successive elements in the array, starting with the first element.

The reason why this algorithm is called 'selection sort' is because in each iteration, the next minimum is 'selected' and consequently swapped.

In this exercise, you have to create a function selection_sort() that takes in a given array and sorts it (in ascending order) using the selection sort algorithm.

Note that the array must be sorted in-place, i.e. the original array must be modified. Moreover, the function must NOT return anything itself.

View Solution

New file

Inside the directory you created for this course on PHP, create a new folder called Exercise-18-Selection-Sort and put the .php solution files for this exercise within it.

Solution

As always, let's start by defining the minimal structure of the selection_sort() function:

<?php

function selection_sort(&$arr) {
   // Code to go here
}

The $arr parameter represents the array that we wish to sort. The reference (&) operator is used because we possibly might have to mutate the array.

If you want to, you can even call the array $nums.

In the outer loop, with $i as its counter variable, we need to iterate from the first to the second last element of the array in search of the correct element for that position.

The last element doesn't need to be considered by this loop since by the time we reach that position, the element sitting there would already be the correct one for that position.

In the inner loop, with $j as its counter variable, we need to go from $i to the end of the array in search of the minimum to be put at the index $i.

This gives us the following code:

<?php

function selection_sort(&$arr) {
   $n = count($arr);

   for ($i = 0; $i < $n; $i++) {
      $min_index = $i;

      for ($j = $i; $j < $n; $j++) {
         if ($arr[$j] < $arr[$min_index]) {
            $min_index = $j;
         }
      }

      $temp = $arr[$min_index];
      $arr[$min_index] = $arr[$i];
      $arr[$i] = $temp;
   }
}

Let's understand the purpose of each variable here:

$n holds the length of $arr. It's only purpose is to cache the value of count($arr) and thus prevent accessing it again and again in the header of both the given loops.
$min_index serves to hold the index of the minimum element found by the inner loop for every $ith iteration. Later on this index is used to access the given element of $arr and swap it with the $ith element.
Since swapping is involved, we need a variable to temporarily hold one of the values. That's what $temp is there for.

The statement $min_index = $i in line 7 serves to set the $ith element as the minimum to start with. After this, the inner loop iterates over the array from $j = $i to $j = $n - 1 in search of the minimum.

In the end, this minimum is placed at the $ith position by means of lines 15 - 17.

Let's try this function:

<?php

function selection_sort(&$arr) { /* ... */ }

$nums = [5, 9, -10, 5, 0, 1, 10];

selection_sort($nums);
print_r($nums);

Array ( [0] => -10 [1] => 0 [2] => 1 [3] => 5 [4] => 5 [5] => 9 [6] => 10 )

Perfect. The numbers are all nicely arranged in ascending order.

Improving the code

Although the code above works perfectly, we can add two little things to make it yet more efficient.

The first is to initialize $j to $i + 1 in the header of the inner loop. This is because the $ith element is already considered in the statement $min_index = $i on line 7.
The second is to only perform the swap if the elements to be swapped aren't at the same position, i.e. $min_index is not equal to $i.

Altogether we get to the following code:

<?php

function selection_sort(&$arr) {
   $n = count($arr);

   for ($i = 0; $i < $n; $i++) {
      $min_index = $i;

      for ($j = $i + 1; $j < $n; $j++) {
         if ($arr[$j] < $arr[$min_index]) {
            $min_index = $j;
         }
      }

      if ($min_index !== $i) {
         $temp = $arr[$min_index];
         $arr[$min_index] = $arr[$i];
         $arr[$i] = $temp;
      }
   }
}

Exercise: Selection Sort