JavaScript Algorithms #2 - Selection Sort

1. What is Selection Sort?

Selection sort is pretty much similar to the bubble sort, but instead of first placing large values into sorted position, selection sort places small values first into the sorted position. So starting from the first element, store it inside a variable and compare its value with the second element. If the second one is smaller, replace the value of variable with the value of second element. And so on, we compare the value of the variable with every element in the array. After the first iteration, we know we have the smallest element in the variable. Swap it with the lowest index element and we have the smallest element in the very front of the element. Repeat this process and iterate through the entire array.

2. Selection Sort Pseudo Code

1. Start the outer loop. We will stop the iteration before it hits the array.length - 1 because once we compare the second last element of the array with the final one, everything will be already sorted.
2. Declare a variable called 'minIndex' to store the index of the smallest value we've seen so far. Let's just assume the first element is the smallest value and store it's index in the 'minIndex' for now.
3. Start the inner loop with the element[i+1]. Since the element[i] will be the standard element that we compare with the next ones, we can start the inner loop iteration with the element[i+1].
4. If a smaller number is found while the iteration, designate the index of that element to be the new minimum and continue until the end of the array.
5. If the value of 'minIndex' is not the index you initially began with, it means new minimum has been found. Swap the two values.
6. Repeat this with the next element until the array is sorted.

   3. Implementing the Selection Sort

function selectionSort(array){
               for(let i = 0; i < array.length - 1; i++){
                   let minIndex = i;
                   for(let j = i + 1; j < array.length; j++){
                       if(array[j] < array[minIndex]){
                           minIndex = j;
                       }
                   }

                   if(minIndex !== i){
                       [array[i], array[minIndex]] = [array[minIndex], array[i]]; //let temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp;
                   }
               }
               return array;
           }

4. Time Complexity of the Selection Sort

The selection sort iterate through the array twice with its outer loop and inner loop, so even in the best case scenario where the array is almost sorted or already sorted and we don't need to swap, it still have quadratic time complexity just by the comparison process. In the worst case scenario, it'll take O(n²) for the comparison and O(n) for the swaps. But still, it has O(n²) of time complexity because according to the Big O notation, O(n²) has the largest contribution and O(n) can be ignored.