How To Do Selection Sort in JavaScript

Sorting algorithms are essential for efficient data manipulation, and Selection Sort is a fundamental sorting algorithm. It’s easy to understand and implement, making it a great starting point for beginners. In this blog post, we’ll review the implementation of Selection Sort in JavaScript, discuss its time and space complexities, and walk through a step-by-step example of how it works.

What is Selection Sort?

Selection Sort works by repeatedly finding the minimum element (considering ascending order) from the unsorted portion of the array and swapping it with the first element in the unsorted section. The algorithm divides the array into two parts: a sorted section and an unsorted section. The sorted section grows as the smallest elements from the unsorted section are moved into it.

Pseudocode for Selection Sort

Here’s the pseudocode that outlines the steps for Selection Sort:

procedure selectionSort(arr)
    for i = 0 to length(arr) - 1 do
        minIndex = i
        for j = i + 1 to length(arr) - 1 do
            if arr[j] < arr[minIndex] then
                minIndex = j
        swap arr[i] with arr[minIndex]

Step-by-Step Explanation:

• The outer loop tracks the position where the next minimum element will be placed (starting from the beginning).
• The inner loop scans the unsorted portion of the array to find the smallest element.
• Once the minimum element is found, it is swapped with the element at the current position.

Time Complexity of Selection Sort

• Best Case: O(n²) – Selection Sort always runs in O(n²), even if the array is already sorted, because it makes comparisons in every pass.
• Average Case: O(n²) – The average performance of Selection Sort is quadratic because the algorithm scans the unsorted portion of the array for each pass.
• Worst Case: O(n²) – The worst case also occurs in O(n²) as Selection Sort always performs the same number of comparisons regardless of the input.

Space Complexity of Selection Sort

• Space Complexity: O(1) – Selection Sort is an in-place sorting algorithm, meaning it only requires a constant amount of extra memory for swapping elements.

JavaScript Implementation of Selection Sort

Here’s the implementation of Selection Sort in JavaScript:

function selectionSort(arr) {
    let n = arr.length;

    for (let i = 0; i < n - 1; i++) {
        // Find the minimum element in the unsorted portion
        let minIndex = i;
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the found minimum element with the first element of the unsorted portion
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }
    return arr;
}

// Example usage
const arr = [29, 10, 14, 37, 13];
console.log("Initial array:", arr);
console.log("Sorted array:", selectionSort(arr));

Explanation:

• The outer loop goes through each element in the array.
• The inner loop finds the smallest element in the unsorted section of the array and records its index (minIndex).
• The current element is then swapped with the element at minIndex.

Output:

Initial array: [ 29, 10, 14, 37, 13 ]
Sorted array: [ 10, 13, 14, 29, 37 ]

Step-by-Step Walkthrough of Selection Sort

Let’s walk through Selection Sort using the array [29, 10, 14, 37, 13].

Step 1: First Element (Index 0)

• We begin by finding the minimum element in the unsorted portion [29, 10, 14, 37, 13].
• Smallest element: 10 at index 1.
• We swap 29 (at index 0) with 10 (at index 1).
• Array after step 1: [10, 29, 14, 37, 13]

---

Step 2: Second Element (Index 1)

• Now, find the minimum element in the remaining unsorted portion [29, 14, 37, 13].
• Smallest element: 13 at index 4.
• We swap 29 (at index 1) with 13 (at index 4).
• Array after step 2: [10, 13, 14, 37, 29]

---

Step 3: Third Element (Index 2)

• The unsorted portion is now [14, 37, 29].
• Smallest element: 14 is already at the correct position, so no swap is needed.
• Array after step 3: [10, 13, 14, 37, 29]

---

Step 4: Fourth Element (Index 3)

• The unsorted portion is [37, 29].
• Smallest element: 29 at index 4.
• We swap 37 (at index 3) with 29 (at index 4).
• Array after step 4: [10, 13, 14, 29, 37]

---

Step 5: Fifth Element (Index 4)

• The last element is already in place.
• Final Sorted Array: [10, 13, 14, 29, 37]

To see how Selection Sort works in practice, go to the Sorting Algorithm Visualizer!

Pros and Cons of Using Selection Sort

Pros:

1. Simple to Implement: Selection Sort is straightforward to understand and code.
2. In-Place Sorting: It doesn’t require extra memory allocation (O(1) space complexity).
3. Good for Small Datasets: Works decently on small arrays where simplicity and clarity matter more than performance.

Cons:

1. Inefficient for Large Arrays: With a time complexity of O(n²), Selection Sort is inefficient for large datasets compared to more advanced algorithms like QuickSort and MergeSort.
2. More Comparisons: Unlike Bubble Sort or Insertion Sort, Selection Sort makes more comparisons regardless of whether the array is sorted.

When to Use Selection Sort

Selection Sort is ideal when:

1. You have small datasets: It’s simple and performs adequately on small arrays.
2. Memory efficiency matters: Selection Sort requires no additional space, as its space complexity is O(1).
3. You need to minimize the number of swaps: While the algorithm performs many comparisons, it has a reduced number of swaps compared to algorithms like Bubble Sort.

However, you would be better off using more advanced algorithms like QuickSort or MergeSort for large datasets.

Conclusion

Selection Sort is easy to understand but inefficient for large arrays due to its quadratic time complexity. However, it’s useful for small datasets or when memory efficiency matters. Learning how it works provides a solid foundation for understanding more advanced sorting algorithms.

Congratulations on reading to the end of this tutorial!

Read the following articles to learn how to implement Selection Sort:

In Python – How to do Selection Sort in Python

In C++ – How to Do Selection Sort in C++

In Java – How to do Selection Sort in Java

Have fun and happy researching!