Selection sort
Selection sort is one of the simplest sorting algorithms. The main idea here is to find the lowest value and move it to the beginning of the array (or find the greatest value and move it to the end). The first step will be to find the smallest item in the array and move it to the beginning. Then, we would simply disregard that item from then on out. After the necessary number of steps, we'd get a sorted array. This algorithm has a bad time complexity and is not stable. However, it's very simple to understand and implement.
Algorithm properties
Time complexity | (n2) |
---|---|
Stability | No |
Speed | Slow |
Note. the time complexity is based on average cases, and the speed is like this when compared to all of the other sorting algorithms.
Process
Consider an array of the following items:
3 | 5 | 2 | 8 | 9 | 1 |
Then, we run a loop through the array from the first to the last item (the range of the loop is highlighted) and we choose the smallest number.
3 | 5 | 2 | 8 | 9 | 1 |
We then swap this number with the first number.
1 | 5 | 2 | 8 | 9 | 3 |
In doing so, we've got the first item of the array sorted. Then, we'll simply run the loop again and find the next smallest item (excluding the smallest one we've just moved to the beginning). To do so we run the loop starting from the second item in the array:
1 | 5 | 2 | 8 | 9 | 3 |
Similarly, we'll sort the item in, and since we already have the first item sorted, we'll swap it with the second item (5).
1 | 2 | 5 | 8 | 9 | 3 |
Now, we have the first two items sorted correctly. We'll just continue doing this - selecting the smallest out of the remaining items and sorting them until we go through the entire array. Here's what the rest of the steps would look like:
1 | 2 | 5 | 8 | 9 | 3 |
1 | 2 | 3 | 8 | 9 | 5 |
1 | 2 | 3 | 8 | 9 | 5 |
1 | 2 | 3 | 5 | 9 | 8 |
1 | 2 | 3 | 5 | 9 | 8 |
1 | 2 | 3 | 5 | 8 | 9 |
That's it! The last item is already sorted, so we can skip this step.
Visualization
Author of the visualization widget is Jenkings
Source code
public static void selectionSort(int[] list) { int temp, min; for (int i = 0; i < (list.length - 1); i++) { min = list.length - 1; // find minimum for (int j = i; j < (list.length - 1); j++) if (list[min] > list[j]) min = j; // swap items temp = list[min]; list[min] = list[i]; list[i] = temp; } }
public static void selectionSort(int[] list) { int temp, min; for (int i = 0; i < (list.Length - 1); i++) { min = list.Length - 1; // find minimum for (int j = i; j < (list.Length - 1); j++) if (list[min] > list[j]) min = j; // swap items temp = list[min]; list[min] = list[i]; list[i] = temp; } }
// sorts the array, assumes indexing from 0 procedure selection_sort(var list: array of integer); var i, j, min, temp: integer; begin for i:=0 to (length(list) - 2) do begin min:=length(list) - 1; // find minimum for j:=i to (length(list) - 1) do if (list[min] > list[j]) then min:=j; // swap items temp:=list[min]; list[min]:=list[i]; list[i]:=temp; end; end;
# returns sorted array def selection_sort(list) (list.length - 1).times do |i| min = list.length - 1 # find minimum i.upto(list.length - 1) do |j| min = j if (list[min] > list[j]) end # swap items temp = list[min] list[min] = list[i] list[i] = temp end end
Comments
No one has commented yet - be the first!