Photo by Iñaki del Olmo on Unsplash

A Breakdown of the Selection Sort Algorithm

When learning various sorting algorithms you will inevitably discover that some perform worse than others. That is the case with “selection sort.” While it ultimately gets the job done, it has an O(n²) time complexity, which does not make it ideal for handling large lists. So, it lags in performance time compared to faster sorting algorithms like “bubble sort” or “merge sort”.

How It Works

Selection sort looks at every value in an array, compares it to the current smallest one, determines which is smallest between the two, and places it at the beginning of the array. It then shifts forward and repeats the same function over the remaining portion of the array until there is nothing left to sort.

Let’s Look at the Code

To set up selection sort, I start with a function that takes in an unsorted array. We can use a for loop to check every element in the array from the beginning until the end. However, we start by assuming that the very first element is the minimum. So, we create a variable that holds the minimum value, calledmin.

const selectionSort = arr => {
  for(let i = 0; i < arr.length; i++){
    let min = i
  }
}

Next, we will need to compare every remaining element in the array to that minimum value minto determine which is smaller. We want it to start comparing immediately after i, so we will create a variable j and make it equal toi + 1. We can use a conditionalif statement to make the comparison. So, if j— the value to the right of min, which is the smallest value thus far — is smaller than min, then we need to swap their order. The nested loop will continue comparing all the other j values to min until it reaches the end of the array. If it finds a value smaller than min, then we need to swap. We accomplish that by first reassigning min to j.

const selectionSort = arr => {
  for(let i = 0; i < arr.length; i++){
    let min = i
    for(let j = i + 1; j < arr.length; j++){
      if(arr[j] < arr[min]){
        min = j
      }
     }
   }
}

However, all that does is reassign the index. We still need to reassign the actual value, or rather, swap the value. So, we will create a temp variable and assign it a value of arr[i]. Then, on the next line, arr[i] will have a value of arr[min], which remember we reassigned to j, so that the smallest value could go first. Last, arr[min] would have a value of temp because it would come to take the place of the second smallest value.

const selectionSort = arr => {
  for(let i = 0; i < arr.length; i++){
    let min = i
    for(let j = i + 1; j < arr.length; j++){
      if(arr[j] < arr[min]){
        min = j
      }
     }
     let temp = arr[i]
     arr[i] = arr[min]
     arr[min] = temp
   }
return arr
}

At this point, the algorithm will sort the array, but it may perform additional unnecessary swaps. To remedy that, we can add another conditional that will check if i is not equal to the minimum value we had at the beginning. If that is the case, only then will it swap. Here’s the full code below: