Selection Sort in PHP

Table of Contents

• About Selection Sort
• Selection Sort Algorithm
• Function
• Time Complexity

About Selection Sort

Selection sort is an in-place comparison-based sorting algorithm. It works by repeatedly finding the minimum element from the unsorted part of the array and swapping it with the first element of the unsorted part. The process continues until the entire array is sorted. It has a time complexity of O(n^2) making it inefficient for large data sets.

Selection Sort Algorithm

The algorithm involves looping and comparing two values and we keep the track of the index of the minimum value.

Steps in a loop:

• We need to track an index of minimum value, so we assign a temporary variable, $min_i, to $i at the beginning of the loop.
• In the loop, we compare the values of $min_i and $j.
• If the value at index $j is less than the value at $i, we change $min_i with the new index of the lesser value at position $j.

Loop #1

We compare the first value (which is 5) with all of the values, and we find that the value at index 1 is less than 5. Once the loop is over, we swap 5 and 1.

Loop #1

Loop #2

Now, the first index is already sorted, so we continue the loop and compare 5 with the rest of the array. We find that 3 is less than 5, and we swap them at the end.

Loop #2

Loop #3

Values 1 and 3 are sorted, but in this last loop, the $min_i does not change (there are no values that are less than 4), so we do not swap. That is also why we have a condition to skip the swap if $i != $min_i.

Loop #3

Final

Function

function selectionSort(array $a): array
{
  for ($i = 0; $i < count($a) - 1; $i++) {
    $min_i = $i;
    for ($j = $i + 1; $j < count($a); $j++) {
      if ($a[$j] < $a[$min_i]) {
        $min_i = $j;
      }
    }
    if ($i != $min_i) {
      $temp = $a[$i];
      $a[$i] = $a[$min_i];
      $a[$min_i] = $temp;
    }
  }
  return $a;
}

// $a = [5, 1, 4, 3];
// selectionSort($a);
// [1, 3, 4, 5]

You can also find the script here:

https://gist.github.com/matusstafura/09c0af86c749f5e5066f920d44f31ba1

Time Complexity

The time complexity of selection sort is O(n^2) where n is the number of elements in the array.

More info: https://en.wikipedia.org/wiki/Selection_sort