Selection Sort Using Javascript

Selection sort

A selection sort , sorts an array by iterating through the array and finding the minimum element(from unsorted array) and then swap the value with current element.

Let’s understand how selection sort works:

suppose we want to sort an array: [64, 25, 14, 21, 55, 101, 12, 22, 11]

• we need to compare each element in the array to find if there exist any element that is less than the current value.
• If their exist a less value then we need to swap the current value and move on to the next element to do the comparison again.
• we’ll repeat this process until we reach the end of the array.

The above added GIF will show you the working of selection sort.

Let’s jump into the code for the implementation of selection sort.

function selection(arr) {
        for (let i = 0; i < arr.length - 1; i++) {
          let lowest;
          let index;
          for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] > arr[j]) {
              if (!lowest) {
                 lowest = arr[j];
                 index = j;
               } else if (arr[j] < lowest) {
                 lowest = arr[j];
                 index = j;
               }
             }
           }
           if (lowest) {
             let value = arr[i];
             arr[i] = lowest;
             arr[index] = value;
             }
        }
return arr;
}

Explanation for what we did: (our unsorted array) [64, 25, 14, 21, 55, 101, 12, 22, 11]

• At line 9, we initialize a for loop till the second last element of the array.(As there is no value to compare if you are at the end of the array)

• At line 10 and 11, we initialise two variable to keep track if any element exist with lower value than the current element.

• At line 12, we initialise another for loop that will run from (i + 1) till the length of the array. (so if our i element is 0 index then our j is i +1).

• From line 13 to 21, we are comparing if the current value is greater than the next value in the array. From line 14 to 17, we are checking if lower value exist in this iteration or not, if not we are setting the current value to lowest value and adding the index as well.

• At line 17, we are checking if previous lowest value exist for this iteration and current value is lower than the previous one, if yes then we update the lowest value and its index variable.

• From line 23 to 27, we are checking if any lowest value exist from this iteration or not, if yes then we perform the swapping. for swapping there is a javascript shortcut:

[arr[i],arr[index]] = [arr[index],arr[i]]

With this approach, we don’t have to consider lowest variable.

• At last out both the for loops, we return the updated sorted array.

Selection sort has a time complexity of O(n*n)

Stay tuned for more to come, If you are new here, do checkout our Algorithms using Javascript blog, we are covering few of the most commonly used algorithms using javascript.

In the next blog, we’ll go through Bubble sort.