Selection sort
Selection sort is an elementary sorting algorithm. It is based on the following simple idea:
Find a smallest element in the array, and swap it with the first one.
Repeat the previous step when considering the sub-array obtained by excluding the first element, until the sub-array consists of only one element.
Some implementations of the algorithm are given below.
def selectionSort(a: Array[Int]) =
val n = a.length
var i = 0
while i < n-1 do
// Find the smallest element in the sub-array a(i..n-1)
var smallestElement = a(i)
var smallestIndex = i
var j = i + 1
while j < n do
if a(j) < smallestElement then
smallestElement = a(j)
smallestIndex = j
j += 1
// Swap the elements at a(i) and a(smallestIndex)
a(smallestIndex) = a(i)
a(i) = smallestElement
// The sub-array a(0..i) is now sorted
i += 1
void selectionsort(std::vector<int>& array) {
const std::size_t n = array.size();
for (std::size_t i = 0; i + 1 < n; i++) {
// Find the smallest element in the sub-array array[i..n-1]
int smallest_element = array[i];
std::size_t smallest_index = i;
for (std::size_t j = i + 1; j < n; j++)
if (array[j] < smallest_element) {
smallest_element = array[j];
smallest_index = j;
}
std::swap(array[i], array[smallest_index]);
}
}
Example: Selection sort
Example: Instability of selection sort
The animation below illustrates that selection sort is not stable. In it, the relative positions of the elements 10 are swapped in the sorting process.
Observe that the algorithm only needs few indices and to store the current minimum element candidate outside the array at any point of time. Thus the amount of extra memory required is \(\Theta(1)\) and the algorithm works in place.
Running time analysis
Running time analysis of the algorithm is quite straightforward. The body of the inner while-loop takes constant time. So do all the other instructions, excluding the inner while-loop, in the outer while-loop. For the outer while-loop index \(i\), the inner loop body is executed \(n-1-i\) times. Thus the running time is \(\sum_{i=0}^{n-2}(c + (n-1-i)d)\), where \(c\) and \(d\) are constants capturing the constant running times of the outer while-loop body (excluding the inner while-loop) and the inner while-loop body. The sum expands to
The asymptotic best-case and worst-case running times are the same as the outer and inner while-loops are always run to the end regardless of the array contents. Thus it is easy to analyze the amount of pairwise element comparisons performed by the algorithm.
For finding the smallest element, the current first element is compared to all the other \(n-1\) elements.
For finding the second smallest element, the current second element is compared to all the other \(n-2\) elements.
And so on.
Therefore, for an array of \(n\) elements, the algorithm always performs \(\sum_{i=1}^{n-1}i = \frac{n(n-1)}{2}\) pairwise element comparisons.
Experimental evaluation
The plots below show the performance of the above selection sort code
when compared to sorting methods found in standard libraries.
When inspecting the plot with logarithmic time scale,
we can see that the gap between the lines increases when the array sizes increase.
Thus there is more than a constant time factor difference between
the running times of the codes.
Based on the plots,
it is obvious that, for instance, the sorted method in Scala implements
an algorithm that scales much better than selection sort.
These experiments were run in a desktop computer with a 6 cores 3.8GHz Intel Xeon W-2235 processor, 32 GiB of memory, Scala 3.3.0 compiler, openjdk 11.0.18 Java virtual machine, and Ubuntu 22.04 operating system.
Generics vs fixed types
By using Scala generics and C++ templates (see also this, this and this), one can build a generic selection sort implementation that works for any comparable object type (floating point numbers, strings, and so on).
def selectionSort[A](a: Array[A])(using ord: math.Ordering[A]) =
val n = a.length
var i = 0
while i < n-1 do
// Find the smallest element in the sub-array a(i..n-1)
var smallestElement = a(i)
var smallestIndex = i
var j = i + 1
while j < n do
if ord.lt(a(j), smallestElement) then // CHANGED
smallestElement = a(j)
smallestIndex = j
j += 1
// Swap the elements at a(i) and a(smallestIndex)
a(smallestIndex) = a(i)
a(i) = smallestElement
// The sub-array a(0..i) is now sorted
i += 1
Above, A is the type of the elements in the array, and
the Ordering ord is used for comparing the array elements.
Note that only two lines have been changed in the code:
the method declaration and the comparison line.
template <typename T, class Compare>
void selectionsort(std::vector<T> &array, Compare lt = std::less<T>{}) {
const std::size_t n = array.size();
for (std::size_t i = 0; i + 1 < n; i++) {
// Find the smallest element in the sub-array array[i..n-1]
T smallest_element = array[i];
std::size_t smallest_index = i;
for (std::size_t j = i + 1; j < n; j++)
if (lt(array[j], smallest_element)) {
smallest_element = array[j];
smallest_index = j;
}
std::swap(array[i], array[smallest_index]);
}
}
Above, T is the type of the elements in the array,
and lt is a binary function such that lt(x,y) returns true
if and only if x is less than y in the applied ordering.
Unfortunately, with current Scala compiler,
the generality does not come without a performance penalty.
As an example,
consider applying the generic selection sort to arrays of integers.
To apply the lt comparison method in the Ordering trait,
each integer fetched from the array is “boxed” (that is, wrapped into an object),
causing a memory allocation and then later garbage collection.
In addition, several virtual function invocations are performed.
We can see the practical effect of this by comparing the running times of our first selection sort working only on integer arrays to those of the generic selection sort algorithm above. If we use logarithmic time scale, we can see that the running times of the generic version are a constant factor (of roughly ten) slower than those of the non-generic integer array version.
In C++, the performance penalty is rather small as the templates are specialized to the required types in the compilation process.