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

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:

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.

We then swap this number with the first number.

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:

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).

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:

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