Sorting an Array Using Selection Sort

Photo by Edu Grande on Unsplash

Selection sort is probably the simplest sorting algorithm (for the programmer not the computer).

The selection sort algorithm stays true to it's name and works by finding the given array's minimum (or maximum - in case of descending sort) number and placing it at the correct position, again and again.

Let's use an example. Consider the following array,

numbers = [5, 4, 3, 2, 1]

For the first step in sorting the numbers array in ascending order, we will need to find the smallest number in the array and move it to it's "rightful" place. We maintain an index i that starts at 0. In a way, we can say that this index divides the array in 2 parts, a sorted part and an unsorted part. Initially the sorted part is empty and the unsorted part contains the complete array. After every iteration we increment the value of i and so, the sorted subarray increases by 1 and the unsorted subarray decreases by one.

Note: This division of array is only virtual. I don't mean that the algorithm actually creates two arrays.

Coming back to our example array,

i = 0
sorted subarray = []
unsorted subarray = [5, 4, 3, 2, 1]

numbers = [5, 4, 3, 2, 1]

In the first iteration we find the smallest number (which is 1) and swap it with the number at index 0 and increase i to 1.

# After first iteration
i = 1
sorted subarray = [1]
unsorted subarray = [4, 3, 2, 5]

numbers = [1, 4, 3, 2, 5] 

This is one iteration. Now we can just repeat this process until all the elements move to the sorted subarray.

# After second iteration
i = 2
sorted subarray = [1, 2]
unsorted subarray = [3, 4, 5]

numbers = [1, 2, 3, 4, 5]

For a human the numbers array is now sorted. But the algorithm doesn't know that, so it continue with the iterations as long as i < N, where N is the length of the array.

# After third iteration
i = 3
sorted subarray = [1, 2, 3]
unsorted subarray = [4, 5]

numbers = [1, 2, 3, 4, 5]

# After fourth iteration
i = 4
sorted subarray = [1, 2, 3, 4]
unsorted subarray = [5]

numbers = [1, 2, 3, 4, 5]

This is the basic premise behind selection sorts. Let's look at the pseudocode now.

FUNCTION SelectionSort(numbers):
    N = length(numbers):
    FOR i = 0; i < N; i++
        
        // Find the smallest number in the unsorted array
        index_of_min = i + 1;
        FOR j = i + 1; j < N; i++
            IF numbers[index_of_min] < numbers[j]:
                index_of_min = j
        
        // Swap the elements numbers[i] and numbers[index_of_min]
        temp = numbers[i]
        numbers[i] = numbers[index_of_min]
        numbers[index_of_min] = temp
        
   RETURN numbers     

If the section where we find the smallest looks strange you can check out the post on finding the smallest number in a given array.

Because we have a nested loop, the complexity of this algorithm is n-squared, O(n ^ 2).


Now that we have seen the pseudocode, go ahead and try it out in the Arena before looking at the code.


Now let's look at how we can implement Selection Sorting in code. Scroll down to find your favorite language. We cover Python, Javascript and Typescript.

Python

def selectionSort(numbers):
  for i in range(len(numbers)):
    # Find the smallest number between i + 1 and len(numbers)
    index_of_smallest = i
    for j in range(i + 1, len(numbers)):
      if(numbers[j] < numbers[index_of_smallest]):
        index_of_smallest = j
    
    # Swap the smallest number with the number at i
    temp = numbers[i]
    numbers[i] = numbers[index_of_smallest]
    numbers[index_of_smallest] = temp
  return numbers

Javascript

function selectionSort(numbers) {
  for(let i = 0; i < numbers.length; i++) {
    // Find the smallest number between i + 1 and len(numbers)
    let indexOfMin = i;
    for(let j = i + 1; j < numbers.length; j++) {
      if(numbers[j] < numbers[indexOfMin]) {
        indexOfMin = j;
      }
    }
    // Swap the smallest number with the number at i
    const temp = numbers[i];
    numbers[i] = numbers[indexOfMin];
    numbers[indexOfMin] = temp;
  }
  return numbers;
}

Typescript

function selectionSort(numbers: numbers[]): numbers[] {
  for(let i = 0; i < numbers.length; i++) {
    // Find the smallest number between i + 1 and len(numbers)
    let indexOfMin = i;
    for(let j = i + 1; j < numbers.length; j++) {
      if(numbers[j] < numbers[indexOfMin]) {
        indexOfMin = j;
      }
    }
    // Swap the smallest number with the number at i
    const temp = numbers[i];
    numbers[i] = numbers[indexOfMin];
    numbers[indexOfMin] = temp;
  }
  return numbers;
}

Now that you know how selection sort works, can you find the problem in this code?

Squash the bug in this selection sort function


Selection sort is good for introduction to sorting algorithms and now that we are done with let's move on to some better, more efficient algorithms.

Hashjar

Hashjar