Sorting Algorithms: Selection Sort

Today we will be discussing Selection Sort! What this algorithm does, is sort the items in place inside the array. Although, that may sound like it would be a fast way to sort an array, selection sort proves you wrong.

The Pseudocode

• Write a function called selectionSort that takes an array as an argument.
• iterate through the array with a variable i. Store the first element as the smallest value seen.
• iterate through the array again with a variable of j at the next index of i.
• if the our value at arr[j] has a smaller value than our lowest variable found, we can assign that value as the lowest.
• if our value at the index of i is not the smallest value encountered. Start the swapping sequence.
• Repeat the same steps with the next element until the array is sorted.

The Code

function selectionSort(arr){
  console.log(arr, 'original')
  for(var i = 0; i < arr.length; i ++){
    var lowest = i

    for(var j = i + 1; j < arr.length; j++){
      if(arr[j] < arr[lowest]){
        lowest = j
      }
    }
    // if our current i is not the lowest value, start switching
     if(i !== lowest){
      //create switch here
      var temp = arr[i]
      console.log(arr)
      arr[i] = arr[lowest]
       console.log(arr)
      arr[lowest] = temp
       console.log(arr)
       console.log(temp, 'temp holding at place for a switch')
       console.log(lowest, 'lowest @ index')
       console.log(arr[i], 'arr[i] has now became lowest')
        console.log(arr[lowest], 'arr[lowest]')
    }
  }
  return arr
  } 

selectionSort([7,9,4])

[ 7, 9, 4 ] 'original'
[ 7, 9, 4 ]
[ 4, 9, 4 ]
[ 4, 9, 7 ]
7 'temp holding at place for a switch'
2 'lowest @ index'
4 'arr[i] has now became lowest'
7 'arr[lowest]'
[ 4, 9, 7 ]
[ 4, 7, 7 ]
[ 4, 7, 9 ]
9 'temp holding at place for a switch'
2 'lowest @ index'
7 'arr[i] has now became lowest'
9 'arr[lowest]'
[ 4, 7, 9 ]

Explanation

The part to understand is how the swap works. Basically, if we find that i is not the lowest value, that's where the magic of swapping happens. If we find out that the value where i is place is not the smallest value, we must create variable temp and assign it in place of arr[i] as a place holder for swapping. We thin assign arr[i] with the value that arr[lowest] is holding. That will now place the smallest value in its correct position. The last swap in place is to assign arr[lowest] to temp, giving the lowest the large value in place close to where it needs to be.

The Time & Space Complexity

Given that our selection sort function has a nested for loop, along with a consistent amount of swapping with every comparison made to every other element in the array, this puts our Time Complexity at O(n^2). However, Space Complexity of this algorithm is O(1), we are swapping in-place of array, which means isn't a need for creating a new array or add extra space in our existing array.

The Conclusion

Well folks, that concludes my blog about Selection Sort! I hope this was helpful on your personal journey of how to understand Algorithms! Stay tuned for the next topic on Insertion Sort!

Happy Coding!