Sort a given array with n elements (integers, strings, etc.).
Sorting is often required in practical applications.
For example, on most online stores you can sort the products by name, price, popularity and other attributes.
There are also some algorithms, like Binary Search, which require sorting as a preprocessing step.
Selection Sort is a great algorithm for sorting relatively small arrays.
It is easy to learn and simple to implement, which makes it perfect for beginners.
If you need to sort a large array, then Selection Sort is not a good choice because of the running time.
The algorithm uses an integer variable current which is illustrated as an arrow below.
Throughout the algorithm, every element left of the arrow (with index < current) is in the correct position.
Set current = 0 and repeat until current = n:
Note: array[current] may be the smallest element with index >= current.
In this case array[current] is already in the correct position and the array will be unchanged.
The swap operation can be a little tricky to implement and many people get it wrong the first time.
Given an array arr and two indices i and j, we want to swap arr[i] and arr[j].
Wrong implementation
The problem is that both arr[i] and arr[j] will contain the same element - the one that was initially at index j.
We need to use a temporary variable to store one of the elements.
Correct implementation
Linear Search is a O(n2) algorithm.
The most expensive part of Selection Sort is finding the smallest element at each step.
In the first step Selection Sort finds the smallest of n elements, then n-1 elements in step 2, n-2 elements in step 3, and so on.
The sum of these numbers have the form: 1+2+3+...+n (written in opposite order).
This well known sum solves to n(n+1)/2 which is roughly n2/2 making Linear Search a quadratic time algorithm.