Selection sort is a sorting technique that selects a list item and then swaps its place with another. It selects the largest item and then swaps it with an item in the highest index of the list.
The algorithm does this repeatedly until the list is sorted. If you're not quite sure how selection sort works, you've come to the right place. We'll explain it in more depth below, along with showing you an example.
Selection Sort: A Closer Look
Suppose you have the list: [39, 82, 2, 51, 30, 42, 7]. To sort the list using selection sort, you would have to first find the highest number in it.
With the given list, that number is 82. Swap 82 with the number in the highest index(that is, 7).
After the first pass, the new list order will be: [39, 7, 2, 51, 30, 42, 82]. Every time the algorithm goes through the whole list, that's called a "pass".
Notice that the list maintains a sorted sublist and an unsorted sublist during the sorting process.
The original list begins with a sorted list of zero items and an unsorted list of all the items. Then after the first pass, it has a sorted list having only the number 82.
At the second pass, the highest number in the unsorted sublist will be 51. This number will be exchanged with 42 to give the new list order below:
[39, 7, 2, 42, 30, 51, 82].
The process is repeated until the whole list is sorted. The figure below summarizes the whole process:
The numbers in bold black show the highest list value at that time. Those in green show the sorted sublist.
Algorithm Analysis
To get the complexity (using Big-O notation) of this algorithm, follow-through below:
On the first pass, (n-1) comparisons are made. On the second pass, (n-2). On the third pass, (n-3) and so on until the (n-1)th pass which makes only one comparison.
Summing up the comparisons as below gives:
(n-1)+ (n-1)+ (n-1)+...+1 = ((n-1)n)/2.
Therefore selection sort is O(n2).
Code Implementation
The code shows functions you can use for performing selection sort using Python and Java.
Python:
def selectionSort(mylist):
for x in range(len(mylist) - 1, 0, -1):
max_idx = 0
for posn in range(1, x + 1):
if mylist[posn] > mylist[max_idx]:
max_idx = posn
temp = mylist[x]
mylist[x] = mylist[max_idx]
mylist[max_idx] = tempJava:
void selectionSort(int my_array[]){
for (int x = 0; x < my_array.length - 1; x++)
{
int index = x;
for (int y = x + 1; y < my_array.length; y++){
if (my_array[y] < my_array[index]){
index = y; // find lowest index
}
}
int temp = my_array[index]; // temp is a temporary storage
my_array[index] = my_array[x];
my_array[x] = temp;
}}Moving On From Selection Sort to Merge Sort
As the algorithm analysis above has shown, the selection sort algorithm is O(n2). It has an exponential complexity and is therefore inefficient for very large data sets.
A much better algorithm to use would be merge sort with a complexity of O(nlogn). And now you know how selection sort works, next up on your study list for sorting algorithms should be the merge sort.
