Javascript Algorithms — Selection Sort

Summary

The provided web content discusses the selection sort algorithm, a simple, comparison-based sorting method with a time complexity of O(n²), which is considered inefficient but easy to implement.

Abstract

The article introduces the selection sort algorithm as part of a series on JavaScript algorithms. Selection sort is characterized as a straightforward, albeit inefficient, sorting algorithm with a time complexity of O(n²), making it comparable in efficiency to bubble sort. The algorithm operates by iteratively selecting the smallest element from the unsorted portion of the array and swapping it with the first unsorted element. This process is repeated until the entire array is sorted. The author provides a JavaScript implementation of the algorithm, emphasizing the importance of avoiding unnecessary swaps by checking if the index of the minimum element is different from the current position before performing the swap.

Opinions

The author considers selection sort to be a very simple and easy-to-implement algorithm.
Despite its simplicity, selection sort is deemed inefficient, though not more so than bubble sort.
The author has a personal preference for optimizing the algorithm by preventing unnecessary swaps of an element with itself.

Javascript Algorithms — Selection Sort

The next algorithm we’ll discuss in this series is selection sort. Selection sort is a very simple, comparison algorithm that runs in O(n²) time. This algorithm is very simple and easy to implement, however it is also very inefficient (though not more so than bubble sort!).

The idea behind selection sort is that you loop through the input array linearly, selecting the first smallest element, and then swap it to the first position. Then you loop through the array again using a linear scan and get the second smallest element, swap it to the second position, and so on and so forth until your array is completely sorted. Easy right? Let’s look at the code:

let selectionSort = (arr) => {
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        let min = i;
        for (let j = i + 1; j < len; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        if (min !== i) {
            let tmp = arr[i];
            arr[i] = arr[min];
            arr[min] = tmp;
        }
    }
    return arr;
}

The code itself is just as easy to read as the concept of selection sort is to explain. A personal preference of mine is to ensure that the value of “min” isn’t equal to “i” in order to avoid an unnecessary swap of the same item with itself (because what’s the point?).

That’s all for the selection sort, thanks for reading!