Fakes

Sorting algorithms: Selection sort

1000 elements to sort.

Sanity check. PHP native sort() algorithm took: 0.002461 seconds. Memory used: 48264 bytes

Running SelectionSort sort. Algorithm took: 0.273260 seconds. Memory used: 48272 bytes

1000 elements to sort.Sanity check. PHP native sort() algorithm took: 0.002461 seconds. Memory used: 48264 bytesRunning SelectionSort sort. Algorithm took: 0.273260 seconds. Memory used: 48272 bytesNext in line of this series: the Selection Sort. This algorithm is not too unlike Insertion Sort, in that it works by putting one element in the right place, at a time. More specifically, selection sort works by making n-1 passes over an n-sized array, each time finding the smallest element and putting it in position n of the array. On the surface it might also look like the bubble sort algorithm: like that, the selection sort does a load of comparisons per pass over the array. However, where bubble sort makes n-1 comparisons per pass of the array, selection sort makes (n-1)-m comparisons per pass, where m is the current pass. In other words, the more passes done, the less comparisons to do.

As a set of steps:

Step 1: set index of array to 0
Step2: find smallest element of array, searching from array index and up
Step 3: swap smallest element with element at array index
Step 4: increase array index

The code

The code for this algorithm is fairly simple - as one might expect. It looks like:

<?php
class SelectionSort extends BaseSort
{
    public function sortFunction()
    {
        $count = count($this->store);
        for ($i = 0; $i < $count - 1; $i++)
        {
            $comparison = $this->store[$i];
            $index = $i;
            for ($ii = $i+1; $ii < $count; $ii++)
            {
                if ($this->store[$ii] < $comparison)
                {
                    $index = $ii;
                    $comparison = $this->store[$ii];
                }
            }
            $this->store[$index] = $this->store[$i];
            $this->store[$i] = $comparison;
        }
    }
}

Again, there's the typical two-loop structure: outer loop and inner loop, matching position in array and sorting comparisons. Looking a bit closer, one can see that this algorithm is stable and that it doesn't use extra memory to sort in (apart from a few extra variables).

Results

1,000 elements first:

1000 elements to sort.
Sanity check. PHP native sort() algorithm took: 0.002461 seconds. Memory used: 48264 bytes
Running SelectionSort sort. Algorithm took: 0.273260 seconds. Memory used: 48272 bytes

At 1,000 elements, it's 13 times slower than the shell sort. It's about twice as slow as the insertion sort algorithm. Next try is 10,000 elements.

10000 elements to sort.
Sanity check. PHP native sort() algorithm took: 0.035268 seconds. Memory used: 505704 bytes
Running SelectionSort sort. Algorithm took: 27.733544 seconds. Memory used: 505704 bytes

100 times slower than at 1,000 elements - the algorithm runs in O(n^2^) as one would expect, given how it works. This is not an algorithm to choose if you've got a lot of elements to sort and limited time. However, the memory footprint does make it nice if you've got limited resources.
Compared to the other algorithms, selection sort runs in about half the time of bubble sort and twice the time of insertion sort. And obviously, massively slower than shell sort.

social