| | |
A selection sort, is in a certain sense somewhat similar to a bubble sort, in that it seeks to move extreme elements in sequence to one side of the array.
The first pass made by the algorithm traverses the entire array to find the position of the smallest element and then swaps that element to the beginning of the array.
In the second pass, knowing that the first element is already in the correct place, we visit all but that first element again to find the second-smallest element, and then swap that element to the second position in the array.
Knowing that the first two elements are now in their correct places, we visit the remaining elements to find the third-smallest element and swap it to the third position in the array.
If we continuing doing this -- after $n-1$ passes the entire array will be correctly sorted.
Below, we show an example of the second version (where we are finding small elements and moving them left, towards the beginning of the array.
=== First Pass ==============================
We are attempting to find the element that
should be at position 0 in the list:
5 2 4 1 9 3 7 min so far = 5, pos = 0
-
5 2 4 1 9 3 7 min so far = 2, pos = 1
-
5 2 4 1 9 3 7 min so far = 2, pos = 1
-
5 2 4 1 9 3 7 min so far = 1, pos = 3
-
5 2 4 1 9 3 7 min so far = 1, pos = 3
-
5 2 4 1 9 3 7 min so far = 1, pos = 3
-
5 2 4 1 9 3 7 min so far = 1, pos = 3
-
5 2 4 1 9 3 7 min so far = 1, pos = 3
-
5 2 4 1 9 3 7 min so far = 1, pos = 3
-
1 2 4 5 9 3 7 after swapping the element at position 3
with the element at position 0
=== Second Pass =============================
We are attempting to find the element that
should be at position 1 in the list:
1 2 4 5 9 3 7 min so far = 2, pos = 1
- note: we ignore the previously placed 1
and start a new search for the next-
smallest value...
1 2 4 5 9 3 7 min so far = 2, pos = 1
-
1 2 4 5 9 3 7 min so far = 2, pos = 1
-
1 2 4 5 9 3 7 min so far = 2, pos = 1
-
1 2 4 5 9 3 7 min so far = 2, pos = 1
-
1 2 4 5 9 3 7 min so far = 2, pos = 1
-
1 2 4 5 9 3 7 after swapping the element at position 1
with the element at position 1
(yes, this is a bit silly, since 2 is
already in the correct position)
=== Third Pass =============================
We are attempting to find the element that
should be at position 2 in the list:
1 2 4 5 9 3 7 min so far = 4, pos = 2
- note: we ignore the previously placed 1 and 2
and start a new search for the next-
smallest value...
1 2 4 5 9 3 7 min so far = 4, pos = 2
-
1 2 4 5 9 3 7 min so far = 4, pos = 2
-
1 2 4 5 9 3 7 min so far = 3, pos = 5
-
1 2 4 5 9 3 7 min so far = 3, pos = 5
-
1 2 3 5 9 4 7 after swapping the element at position 5
with the element at position 2
=== Fourth Pass =============================
We are attempting to find the element that
should be at position 3 in the list:
1 2 3 5 9 4 7 min so far = 5, pos = 3
- note: we ignore the previously placed 1, 2, and 3
and start a new search for the next-
smallest value...
1 2 3 5 9 4 7 min so far = 5, pos = 3
-
1 2 3 5 9 4 7 min so far = 4, pos = 5
-
1 2 3 5 9 4 7 min so far = 4, pos = 5
-
1 2 3 4 9 5 7 after swapping the element at position 5
with the element at position 3
=== Fifth Pass =============================
We are attempting to find the element that
should be at position 4 in the list:
1 2 3 4 9 5 7 min so far = 9, pos = 4
- note: we ignore the previously placed numbers 1-4
and start a new search for the next-
smallest value...
1 2 3 4 9 5 7 min so far = 5, pos = 5
-
1 2 3 4 9 5 7 min so far = 5, pos = 5
-
1 2 3 4 5 9 7 after swapping the element at position 5
with the element at position 4
=== Sixth Pass ============================
We are attempting to find the element that
should be at position 5 in the list:
1 2 3 4 5 9 7 min so far = 9, pos = 5
- note: we ignore the previous placed numbers 1-5
and start a new search for the next-
smallest value...
1 2 3 4 5 9 7 min so far = 7, pos = 6
-
1 2 3 4 5 7 9 after swapping the element at position 6
with the element at position 5
===========================================
There is only one other value to consider (9), but there is only
one position he could be in -- and he's in it. Thus, we are done
sorting the array.
Again, the implementation of the algorithm is fairly straight-forward, using the helper methods less() and exch() mentioned previously. The version shown below is the one consistent with the example above, where small elements are swapped towards the beginning of the array.
public static void selectionSort(Comparable[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
int minPos = i;
for (int j = i+1; j < n; j++) {
if (less(a[j],a[minPos])) {
minPos = j;
}
}
exch(a,i,minPos);
}
}
As for the cost, let us again focus on the number of comparisons and exchanges. With regard to comparisons made, we are always making $n-1$ comparisons in the first pass, $n-2$ comparisons in the second pass, $n-3$ in the third, and so on... Thus, we have a total number of comparisons given by:
$$(n-1) + (n-2) + (n-3) + \cdots + 3 + 2 + 1 = \frac{n(n-1)}{2} \sim \frac{n^2}{2}$$Importantly, note that the running time to sort $n$ elements with a selection sort is not affected by the order of the elements -- it will be quadratic time, even if the input is already sorted!
Now let us consider the number of exchanges. Since we know that
Since there are only a linear number of exchanges for sorting $n$ elements, the "data movement" in a selection sort is minimal.
Note, the bubble sort actually faired a bit better in terms of comparisons, as while it was also $O(n^2)$ on average, there were times (like when the array is already partially ordered) when far fewer comparisons are made. However, when we consider the number of exchanges, we see that selection sort far surpasses the lowly bubble sort.