Selection Sort in JavaScript - Complete Guide

Introduction

The Selection Sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array:

• The subarray which is already sorted.
• Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

Flowchart of the Selection Sort

How Selection Sort Works?

Let's consider the following array as an example: arr[] = [64, 25, 12, 22, 11]

First Pass:

• For the first position in the sorted array, the whole array is traversed from index 0 to 4 sequentially. The first position where 64 is stored presently, after traversing the whole array it is clear that 11 is the lowest value.

• Thus, replace 64 with 11. After one iteration 11, which happens to be the least value in the array, tends to appear in the first position of the sorted list.

  [11, 25, 12, 22, 64]

Second Pass:

• For the second position, where 25 is present, again traverse the rest of the array in a sequential manner.

• After traversing, we found that 12 is the second lowest value in the array and it should appear at the second place in the array, thus swap these values.

  [11, 12, 25, 22, 64]

Third Pass:

• Now, for the third place, where 25 is present again traverse the rest of the array and find the third least value present in the array.

• While traversing, 22 came out to be the third least value and it should appear at the third place in the array, thus swap 22 with element present at third position.

  [11, 12, 22, 25, 64]

Fourth Pass:

• Similarly, for the fourth position traverse the rest of the array and find the fourth least element in the array.

• As 25 is the 4th lowest value hence, it will place at the fourth position.

  [11, 12, 22, 25, 64]

Fifth Pass:

• At last the largest value present in the array automatically gets placed at the last position in the array.

• The resulted array is the sorted array.

  [11, 12, 22, 25, 64]

Approach

• Initialize minimum value (min_idx) to location 0
• Traverse the array to find the minimum element in the array
• While traversing if any element smaller than min_idx is found then swap both the values (update min_idx).
• Then, increment min_idx to point to the next element (outer loop advances)
• Repeat until the array is sorted

Implementation

Below is the basic implementation of the above approach in JavaScript:

function selectionSort(arr, n) {
    for (let i = 0; i < n; i++) {
        // Find the minimum element in unsorted array
        let min_idx = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // Swap the found minimum element with the first element
        let temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
    return arr;
}
 
// Example usage:
let arr = [2, 1, 3, 4];
let sortedArr = selectionSort(arr, 4);
console.log(sortedArr); // Output: [1, 2, 3, 4]

Modern ES6 Implementation

Here is a cleaner ES6 version using array destructuring for swapping:

function selectionSortES6(arr) {
    const n = arr.length;
    
    for (let i = 0; i < n - 1; i++) {
        let min_idx = i;
        
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        
        // Only swap if a new minimum was found
        if (min_idx !== i) {
            [arr[i], arr[min_idx]] = [arr[min_idx], arr[i]];
        }
    }
    
    return arr;
}
 
const numbers = [64, 25, 12, 22, 11];
console.log('Original Array:', numbers);
console.log('Sorted Array:', selectionSortES6([...numbers]));

Time & Space Complexity Analysis

Time Complexity

• Best Case: O(n²) - Even if the array is already sorted, the algorithm will still traverse the remaining array to find the minimum element for every position.
• Average Case: O(n²) - When elements are in random order.
• Worst Case: O(n²) - When the array is in reverse order.

Why is it always O(n²)? For an array of n elements:

• Pass 1: n-1 comparisons
• Pass 2: n-2 comparisons
• ...
• Total comparisons = (n-1) + (n-2) + ... + 1 = n(n-1)/2, which simplifies to O(n²).

Space Complexity

• Auxiliary Space: O(1) - Selection sort is an in-place sorting algorithm. It only requires a constant amount of extra memory space (for variables like i, j, min_idx, and temporary swap variables).

Key Characteristics of Selection Sort

• Not Stable: The default implementation of Selection Sort is not a stable sorting algorithm. It can change the relative order of equal elements because it swaps non-adjacent elements over large distances.
• In-place Sorting: Yes, it does not require extra auxiliary space.
• Comparison-based Algorithm: Yes, it works by explicitly comparing elements.
• Good for Minimal Swaps: It never makes more than O(n) swaps. It can be useful when memory write operations are significantly more expensive than read operations.

Comparison with Bubble Sort