Selection Sort

If you've never heard of selection sort, it's basically the opposite of bubble sort with less swapping. If you don't know bubble sort, you can refer to my guide on bubble sort.

How Selection Sort Works

Selection sort works by looping over every item in the array to find the smallest value, storing its index in a variable, and then swapping it to the appropriate position in the array, from start to end. For swapping, you can define a function that does just that, as you'll probably reuse it:

function swap(array, idx, idx2) {
  let temp = array[idx];
  array[idx] = array[idx2];
  array[idx2] = temp;
}

We basically create a temporary value to store the first value, then override the first value with the second one, and finally use the stored value to override the second value.

Implementing Selection Sort

Now that we have the swap function, how can we implement selection sort?

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) min = j;
    }
    if (i !== min) swap(arr, i, min);
  }
  return arr;
}

Here’s a step-by-step breakdown of the implementation:

• Outer Loop: We loop over each element in the array.
• Initialize Minimum Index: On each iteration, we create a variable min that stores the index of the smallest value.
• Inner Loop: We loop again, but this time from the next element (i + 1) to the end of the array. This is because it makes no sense to compare an element to itself or to the already sorted part of the array.
• Find Minimum: If we find a value smaller than the current minimum, we update min to be the current index.
• Swap: After the inner loop, we swap the smallest value with the value at the outer loop index, but only if min has changed.

After every iteration, the smallest item in the current subarray is moved to the beginning (first from start to end, then from start + 1 to end, and so on).

Sorting an Array of Objects

Selection sort can also be used to sort an array of objects based on a specific property. Here’s an example of sorting an array of objects by the age property:

function selectionSortObjects(arr, key) {
  for (let i = 0; i < arr.length; i++) {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j][key] < arr[min][key]) min = j;
    }
    if (i !== min) swap(arr, i, min);
  }
  return arr;
}

const people = [
  { name: 'Alice', age: 30 },
  { name: 'Bob', age: 25 },
  { name: 'Charlie', age: 35 }
];

console.log(selectionSortObjects(people, 'age')); // [{"name":"Bob","age":25},{"name":"Alice","age":30} {"name":"Charlie","age":35}]

Performance Considerations

Selection sort is not the most efficient algorithm due to its time complexity of O(n²). Although technically we loop over an always smaller subarray, for large datasets, this inefficiency becomes significant.

Key Points to Consider:

• Worst-case scenario: O(n²) In the worst-case scenario, where the array is in reverse order, selection sort will have to perform the maximum number of comparisons and swaps. This results in a time complexity of O(n²), where n is the number of elements in the array.
• Best-case scenario: O(n²) In the best-case scenario, where the array is already sorted, selection sort will not have to swap anything. However, the number of iterations remains the same, resulting in a time complexity of O(n²)
• Average-case scenario: O(n²) On average, selection sort will still require the same number of iterations and a significant number of comparisons and swaps, resulting in an average time complexity of O(n²).

Practical Use Cases

Selection sort works well for small arrays or cases where minimizing swaps matters (it performs at most n-1 swaps). It is not suitable for large datasets due to its O(n²) time complexity.

Conclusion

Selection sort is generally not suitable for large datasets due to its inefficiency. However, it can be useful for educational purposes or for sorting small arrays where simplicity and readability are more important than performance. It's always good to have multiple sorting algorithms in your toolkit, and selection sort is a great starting point for understanding more complex sorting techniques.

Happy coding ! 👨🏻‍💻