Selection Sort Algorithm - DSA and Algorithm - JavaScript

 

The Selection Sort algorithm is a very interesting question that you may have heard in your school or college asked in many interviews including FAANG companies.

Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.

Selection Sort Working:

1. Set the first element as a minimum.

2. Compare the minimum with the second element. If the second element is smaller than the minimum, assign the second element as the minimum.

Compare minimum with the third element. Again, if the third element is smaller, then assign a minimum to the third element otherwise do nothing. The process goes on until the last element.

3. After each iteration, the minimum is placed in the front of the unsorted list.

4. For each iteration, indexing starts from the first unsorted element. Steps 1 to 3 are repeated until all the elements are placed in their correct positions.

Let's start with the algorithm,

var selectionSort = function(array){

    var i, j, minIndex;

 

   // loop to iterate over the entire array

   for (i = 0; i < array.length - 1; i++)

   {

       // set minIndex equal to the first unsorted element

       minIndex = i;

       // iterate over unsorted sublist

       for (j = i + 1; j < array.length; j++)

       {

         if (array[j] < array[minIndex])

         {

              minIndex = j;

         }

     }

       // swapping the minimum element with the element at minIndex

       var temp = array[minIndex];

       array[minIndex] = array[i];

       array[i] = temp;

   }

    return array;

}

Time Complexities:

• Worst Case Complexity O(n²): If we want to sort in ascending order and the array is in descending order then, the worst case occurs.

• Best Case Complexity O(n): It occurs when the array is already sorted

• Space Complexity O(n²):  It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

I hope you understood the algorithm. If you have any doubts, please let us know in the comments.