JavaScript

Selection Sort in JavaScript

The selection sort algorithm sorts the list by finding the smallest number from the unsorted list and moving it in the sorted list. Selection sort divides the actual list into two lists, one for sorted numbers while the second list is for the remaining unsorted numbers, initially we considered the whole list as an unsorted list.

Selection sort works on a very basic philosophy that is to find the smallest number in the array and swap it to the initial position (0th index), then again find the second smallest number from the remaining unsorted array and place it to the appropriate position (first index) and so on, in this way finally, we will get a sorted array.

In this article, we will discuss how selection sort works, for this purpose we will consider an example to explain each step for sorting an array using selection sort.

How Selection Sort Works

For instance, consider the following array and sort it using selection sort:

Step 1

Initially, we have an array of five elements, at index zero we have a value ‘9’, and we will compare it to the next index, if the value of the first index is less than the value of zero-index then next we will compare the value of index 1 to the remaining array elements.

We compare ‘1’ with ‘8’, ‘1’ is less than ‘8’ so again we will compare ‘1’ with the value of the next index (3rd index),

‘1’ is less than ‘2’.

It means again ‘1’ will be compared with the last index where we found a value ‘4’ which is also greater than ‘1’.

So step by step we compare 1 with each element of the array, as a result, we witnessed that ‘1’ is the smallest number among all the array elements.

So finally we got a sorted value for the index 0.

Step 2:

Now after step 1 the value at index zero is sorted, so we have two arrays now, at the left side a sorted array and on the right side an unsorted array:

We will sort the unsorted array, so initially we will compare index one with index two, we found ‘9’ is greater than ‘8’

As ‘8’ is less than ‘9’, so from here we will compare the value of index 2 which is ‘8’ with the other array elements. Now ‘8’ is compared with ‘2’

‘2’ is less than ‘8’ therefore in the next iteration we will compare ‘2’ with the last array elements. Compare ‘2’ with ‘4’:

So, ‘2’ is the smallest element among all the unsorted array elements, so, will be swapped at the second index, resultant array after the second step will be:

Step 3

So far we have 2 elements sorted while still, three elements are unsorted, now we will sort the remaining unsorted elements of the array, for this purpose, compare the value of index 2 with the value of index 3, so there will be no change as ‘8’ is less than ‘9’ and in next iteration, we compare ‘8’ with the value of final index.

Compare ‘8’ with ‘4’, here ‘4’ is less than ‘8’ and ‘4’ is the last element of the array, therefore ‘4’ will be swapped with ‘8’: and the updated array will be:

Step 4:

Now, the first three elements are sorted, compare the value of index 3 with the value of index 4, here ‘9’ is greater than ‘8’ and there is no more element left in the array for the comparison, therefore we swapped the value of forth index with the value of the third index:

Finally, we get a sorted array, moreover, if someone is instructed to sort in descending order then it will be done in reverse order by finding the maximum value.

How to implement Selection Sort in JavaScript

Now, we will conclude the working of selection sort in terms of each step or each pass and then we will implement the same concept in JavaScript.

After completing the first step, we get minimum value at 0th index, in the second step second smallest number is shifted at the first index, similarly, we get a proper number at the proper index after completing the third and fourth step, we don’t need to perform sorting for the last index as we have only one element left and if all the prior elements in the array are sorted then the last element will also be sorted. Hence, we concluded that we require a total of “n-1” passes to sort an array. Now we will implement this concept of selection sort in JavaScript:

function selection_Sort(input_Array) {

    let array_length = input_Array.length;    

    for(let i = 0; i < array_length; i++) {

        let smallest = i;

        for(let j = i+1; j < array_length; j++){

            if(input_Array[j] < input_Array[smallest]) {

                smallest=j;

            }

         }

         if (smallest != i) {

             let temp_val = input_Array[i];

             input_Array[i] = input_Array[smallest];

             input_Array[smallest] = temp_val;      

        }

    }

    return input_Array;

}

const input_Array = [9, 1, 8, 2, 4];

selection_Sort(input_Array);

console.log("Final sorted array : ",input_Array);

In the initial part of the code, we utilize the “.length” property to check the length of the actual array and store it in a variable “array_length” then we iterate the loop until it reaches the “n-1” index. In the loop initially, we consider that the current index has the smallest value, therefore, we set “smallest=i” and next we use another for-loop to compare the current value to the remaining values of the array, and the loop will start from is “i+1”. Next, we write the code for swapping the element once we found the smallest element in the array.

Finally, we utilized the console.log function to print the output on the browser’s console:

Conclusion

In this article, we have learned how to sort an array using selection sort in JavaScript. In the selection sort algorithm, we pick the first element of the list or array and compare it with the rest of the array elements when we found the smallest element we shift it to the initial index then shift the second least element to the first index, and so on, as a result, we got an array where the sorted elements are present at the left side and the unsorted elements are present at the right side of the array. In this way, a final sorted array is constructed using selection sort in JavaScript. We understand the logic behind the selection sort algorithm by considering an example and explaining its working step-by-step. Once we understand how selection sort works then we implement it in JavaScript.

About the author

Shehroz Azam

A Javascript Developer & Linux enthusiast with 4 years of industrial experience and proven know-how to combine creative and usability viewpoints resulting in world-class web applications. I have experience working with Vue, React & Node.js & currently working on article writing and video creation.