Implementation of Selection Sort Algorithm in JavaScript

Selection sort is a simple sorting algorithm that works by repeatedly picking the smallest element from a list and moving it to the beginning of unsorted portion of the list. In this article, we’ll explore how to implement this algorithm in JavaScript. We’ll start with a simple implementation and then look at some practical variations, like sorting in descending order and sorting custom objects.

Prerequisites:

Basic Selection Sort Implementation

Let’s begin with a basic version of the selection sort algorithm. This code will sort an array of numbers in ascending order. We’ll go through each step, so it’s easy to follow, even if you’re just starting out with JavaScript.

function selectionSort(arr) {
  // `arr`: This is the array you want to sort
  let n = arr.length;
  // `n`: This variable stores the number of items in the array

  // We go through each item in the array, except the last one
  // The outer loop iterates from the first element (`0`) to the second-to-last element (`n - 2`).
  for (let i = 0; i < n - 1; i++) {
    // Let's say the current item is the smallest
    // `minIndex`: This will hold the index of the smallest item we find
    let minIndex = i;

    // Now, check the rest of the array to find a smaller item
    // The inner loop iterates through the unsorted portion of the array,
    // starting from the element next to the current one (`i + 1`) to the last element (`n - 1`).
    for (let j = i + 1; j < n; j++) {
      // If we find a smaller item
      if (arr[j] < arr[minIndex]) {
        // Update the index of the smallest item
        minIndex = j;
      }
    }

    // If the smallest item is not the current item, swap them
    if (minIndex != i) {
      // ES6 way to swap variables
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  // Now the array is sorted!
  return arr;
}

// Let's create an array
let myList = [64, 25, 12, 22, 11];
console.log("Original array: " + myList);

// Sort the array using selection sort
let sortedList = selectionSort(myList);

// Print the sorted array
console.log("Sorted array: " + sortedList); // Output: Sorted array: 11,12,22,25,64

Let’s break down this code step by step:

  1. Outer Loop: The outer loop for (let i = 0; i < n - 1; i++) goes through each element in the array, except the last one. In each iteration, we assume that the current element at index i is the smallest in the unsorted part of the array. We stop at n - 2 because the last element will automatically be in its correct position after the n - 1 element is sorted.
  2. Inner Loop: The inner loop for (let j = i + 1; j < n; j++) checks the rest of the array to find a smaller element. If it finds one (if (arr[j] < arr[minIndex])), it updates the index of the smallest element (minIndex = j).
  3. Swapping: After the inner loop, we check if the smallest element is not the current element (if (minIndex != i)). If they are different, we swap the current element with the smallest element. This puts the smallest element in its correct position. Here, we use the ES6 destructuring assignment to swap the elements: [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];.

Sorting in Descending Order

What if we want to sort the array in descending order (from largest to smallest)? We just need to make a small change in the comparison within the inner loop. Here’s how:

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

  for (let i = 0; i < n - 1; i++) {
    let maxIndex = i;

    for (let j = i + 1; j < n; j++) {
      // If we find a larger item
      if (arr[j] > arr[maxIndex]) { // Note the change here: `>` instead of `<`
        // Update the index of the largest item
        maxIndex = j;
      }
    }

    if (maxIndex != i) {
      [arr[i], arr[maxIndex]] = [arr[maxIndex], arr[i]];
    }
  }
  return arr;
}

// Let's create an array
let myList = [64, 25, 12, 22, 11];
console.log("Original array: " + myList);

// Sort the array in descending order using selection sort
let sortedList = selectionSortDescending(myList);

// Print the sorted array
console.log("Sorted array (descending): " + sortedList); // Output: Sorted array (descending): 64,25,22,12,11

The only difference is in the if condition inside the inner loop: if (arr[j] > arr[maxIndex]). This change makes the function find the largest element instead of the smallest.

Sorting Custom Objects

Selection sort isn’t just for numbers; it can also sort custom objects. Imagine you have an array of objects, each representing a person with a name and an age. You might want to sort these people by their age or alphabetically by their name. Here’s how you can achieve this using JavaScript.

function selectionSortCustom(arr, compare) {
  let n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < n; j++) {
      // Use the compare function to compare
      if (compare(arr[j], arr[minIndex]) < 0) {
        minIndex = j;
      }
    }

    if (minIndex != i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
}

// Let's create an array of objects
let people = [
  { name: "Alice", age: 30 },
  { name: "Bob", age: 25 },
  { name: "Charlie", age: 35 }
];

console.log("Original array:");
people.forEach(person => console.log(person.name + " (" + person.age + ")"));

// Sort by age
selectionSortCustom(people, (a, b) => a.age - b.age);
console.log("\nSorted by age:");
people.forEach(person => console.log(person.name + " (" + person.age + ")"));

// Sort by name
selectionSortCustom(people, (a, b) => a.name.localeCompare(b.name));
console.log("\nSorted by name:");
people.forEach(person => console.log(person.name + " (" + person.age + ")"));

In this example, the selectionSortCustom function takes an additional compare argument. This compare argument should be a function that tells the sort function how to compare the objects.

  • Sorting by Age: When sorting by age, (a, b) => a.age - b.age tells the function to subtract the ages of two Person objects. If the result is negative, a is considered smaller. If the result is positive, b is considered smaller.
  • Sorting by Name: When sorting by name, (a, b) => a.name.localeCompare(b.name) tells the function to use the localeCompare method to compare the names of two Person objects alphabetically.

This approach makes selection sort very flexible, allowing you to sort arrays of any type of objects based on any criteria you define. Just pass the appropriate compare function. The localeCompare method is used for comparing strings, and it handles international characters correctly.

What’s Next?

Now that you’ve learned how to implement selection sort in JavaScript, you can explore further: