Understanding Selection Sort Algorithm

Selection sort is a simple and intuitive sorting algorithm that can be used to sort elements in an array. It works by repeatedly finding the minimum element from the unsorted part of the array and swapping it with the element at the beginning of the unsorted portion.

How does Selection Sort work?

The selection sort algorithm divides the array into two parts: sorted and unsorted. Initially, the sorted part is empty, and the unsorted part contains all the elements. The algorithm works by repeatedly selecting the minimum element from the unsorted portion and placing it at the end of the sorted portion. This process continues until the array is completely sorted.

To better understand selection sort, let’s consider an example. Suppose we have an array [5, 3, 8, 2, 1]. Here are the step-by-step iterations of the selection sort algorithm:

1. Iteration 1: Find the minimum element in the unsorted portion (i.e., [5, 3, 8, 2, 1]), which is 1. Swap it with the element at the beginning (i.e., index 0) of the unsorted portion. The array becomes [1, 3, 8, 2, 5].

2. Iteration 2: Find the minimum element in the remaining unsorted portion (i.e., [3, 8, 2, 5]), which is 2. Swap it with the element at index 1 of the unsorted portion. The array becomes [1, 2, 8, 3, 5].

3. Iteration 3: Find the minimum element in the remaining unsorted portion (i.e., [8, 3, 5]), which is 3. Swap it with the element at index 2 of the unsorted portion. The array becomes [1, 2, 3, 8, 5].

4. Iteration 4: Find the minimum element in the remaining unsorted portion (i.e., [8, 5]), which is 5. Swap it with the element at index 3 of the unsorted portion. The array becomes [1, 2, 3, 5, 8].

   Writing Factorial Recursively

5. Iteration 5: Find the minimum element in the remaining unsorted portion (i.e., [8]), which is 8. Swap it with the element at index 4 of the unsorted portion. The array remains unchanged as the last element is already in its correct position.

After these iterations, the array becomes sorted in ascending order: [1, 2, 3, 5, 8].

Implementing Selection Sort in JavaScript

Let’s now look at how we can implement the selection sort algorithm using JavaScript:

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

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

    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

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

  return arr;
}

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

In the code above, we define the selectionSort function to perform the selection sort algorithm. The function takes an array as input and returns the sorted array. The outer loop iterates through the array, and for each iteration, the inner loop finds the minimum element in the unsorted portion. If a smaller element is found, it is swapped with the current element.

Conclusion

Selection sort is a straightforward sorting algorithm that is easy to understand and implement. Although it is not the most efficient sorting algorithm for large datasets, it can be useful for small arrays or when simplicity is preferred. Understanding the selection sort algorithm provides a foundational understanding of sorting algorithms in general, which is essential for any computer science or software development role.