Matus Stafura

Posted on

# Selection Sort in PHP

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.