Selection Sort

Selection sort is another simple sorting algorithm that works by dividing the array into two parts: the sorted part and the unsorted part. The sorted part gradually grows from left to right, while the unsorted part shrinks from right to left.

Algorithm

Let's take a look at the steps for selection sort, assuming we are sorting in ascending order:

1. The algorithm divides the array into two parts: the sorted part and the unsorted part. We can imagine the sorted part on the left and the unsorted part on the right. Initially, the sorted part is empty, and the unsorted part contains the entire array.
2. In each pass, the algorithm scans the unsorted part of the array to find the smallest element in that part.
3. Once the smallest element is identified, it is swapped with the leftmost element of the unsorted part (the element at the boundary of the sorted and unsorted parts).
4. After the swap, the boundary between the sorted and unsorted parts is shifted one position to the right. The selected element is now considered part of the sorted part, and the unsorted part is reduced by one element.
5. Steps 2 to 4 are repeated until the unsorted part contains just one element, which means it must be sorted. Consequently, the entire array is sorted.

---

Walkthrough

Let's consider an array: [3, 8, 2, 1].

Pass 1

• Initially, the sorted section is empty, and the unsorted section contains all the elements: [3, 8, 2, 1]. In the first pass, we will iterate over the unsorted section, searching for the smallest element.

• In the first iteration, the current element is 3, which is the smallest element encountered so far. Therefore, we set minIndex to its index value, 0.

• In the second iteration, the current element is 8. Since it's greater than the element at minIndex, we continue without making changes.

• In the third iteration, the current element is 2. This is smaller than the element at minIndex, so we update minIndex to point to index 2.

• In the final, fourth iteration, the current element is 1. It's smaller than the element at minIndex, so we update minIndex to index 3.

• Having completed the iterations to find the smallest element, the next step is to swap the first element of the unsorted section — the leftmost element — with the element at minIndex. After this swap, the boundary between the sorted and unsorted sections shifts by one position. Consequently, the sorted section now includes element 1, and the unsorted section contains elements [8, 2, 3].

Let's continue with the second pass through the array.

Pass 2

• The sorted part now contains [1], and the unsorted part contains the elements [8, 2, 3]. In the second pass, we search for the smallest element in the unsorted section [8, 2, 3].

• In the first iteration, the current element is 8, which is the smallest element encountered so far. Therefore, we set minIndex to its index value, 1. Note that even though we've 'split' the array, this doesn't effect the index positions of our unsorted section. The index of 8 is 1, not 0.

• In the second iteration, the current element is 2. Since it's smaller than the element at minIndex, we update minIndex to point to index 2.

• In the final, third iteration, the current element is 3. It's greater than the element at minIndex, so we do not make any changes.

• Having completed the iterations, the next step is to swap the first element of the unsorted section with the element at minIndex. After this swap, the boundary between the sorted and unsorted sections shifts by one position. Consequently, the sorted section now contains [1, 2], and the unsorted section contains elements [8, 3].

Moving on to the third and final pass.

Pass 3

• The sorted part now contains the elements [1, 2], and the unsorted part contains the elements [8, 3]. In the third pass, we search for the smallest element in the unsorted section [8, 3].

• In the first iteration, the current element is 8, which is the smallest element encountered so far. Therefore, we set minIndex to its index value, 2.

• In the second iteration, the current element is 3. Since it's smaller than the element at minIndex, we update minIndex to point to index 3.

• At the end of the last iteration, the minIndex points to the last element of the array.

• The next step is to swap the first element of the unsorted section with the element at minIndex. After this swap, the boundary between the sorted and unsorted sections shifts by one position. After the third pass, the unsorted part contains only one element, which means that the array is sorted.

We can see that the array is now fully sorted in ascending order: [1, 2, 3, 8].

---

Code Implementation

Here's the code implementation of the selection sort algorithm in JavaScript:

function selectionSort(arr) {
  const len = arr.length;

  for (let i = 0; i < len - 1; i++) {
    // Initialize `minIndex` as the first element in
    // the unsorted portion of the array
    let minIndex = i;

    // Iterate over the rest of the unsorted part of the array
    for (let j = i + 1; j < len; j++) {
      // Check if the element in the current iteration is
      // less than the element at the current `minIndex`
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // If the minimum element is already at
    // index `i`, we don't need to swap
    if (minIndex !== i) {
      // Swap the first element of the unsorted portion
      // with the element at `minIndex`
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

const array = [3, 8, 2, 1];
console.log(selectionSort(array)); // Output: [1, 2, 3, 8]

Selection sort has a time complexity of O(N^2), where N is the number of elements in the array. This means that the time it takes to sort the array grows quadratically with the input size.

At first glance, it may seem that Bubble Sort and Selection Sort are equally efficient in the worst-case scenario. However, Selection Sort has its own specific use cases.

Selection sort can be superior to Bubble sort in terms of performance when the cost of swapping elements is significantly higher than the cost of comparisons, as it makes a maximum of N swaps for an array of size N.

In bubble sort, swaps occur whenever adjacent elements are out of order, potentially leading to a relatively large number of swaps. On the other hand, selection sort minimizes the number of swaps by performing only a single swap after finding the smallest element in each pass. This reduction in the total number of swaps makes selection sort more efficient, particularly when the cost of swapping elements is high.

Therefore, although neither algorithm is considered efficient for large datasets, if one were to choose between Selection Sort and Bubble Sort, Selection Sort would be the preferable option when the swapping operation is costly.