Sorting Algorithms: Selection Sort
Published: 2021-04-02 05:09:08

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 
```Javascript 
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])
```

```javascript
[ 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!