DEV Community

loading...
Cover image for Sorting Algorithms: Selection Sort

Sorting Algorithms: Selection Sort

keeks5456 profile image keeks5456 ・3 min read

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])
Enter fullscreen mode Exit fullscreen mode
[ 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 ]
Enter fullscreen mode Exit fullscreen mode

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!

Discussion (0)

Forem Open with the Forem app