Selection Sort: The Persistence to Find the Minimum

Chris just tried sorting 100 data items using the Bubble Sort he learned recently.

The result was shocking. If luck is not on his side, it swaps positions thousands of times to complete the sort.

"Wait, can't we just find the smallest number and move it to the front just once?"

"Why waste energy constantly swapping with the neighbor?"

Chris's intuition was correct. The method that drastically reduces the brute-force swap count of Bubble Sort is Selection Sort.

1. "I'll Pick Only You"

The idea behind Selection Sort is very human. It is similar to the method we unconsciously use when organizing cards.

If Bubble Sort is "I swap if I am bigger than my neighbor,"

Selection Sort is "I scan to the end, Select the smallest one, and bring it over."

2. Implementing in JavaScript

When implementing in code, you need a variable to remember "the location (index) of the minimum value found so far."

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    // 1. Assume the current position (i) is the smallest for now.
    let lowest = i;

    // 2. Scan from i+1 to the end to find the real minimum.
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j; // "Found it! You are the new minimum."
      }
    }

    // 3. Swap only if the minimum is not the current position.
    // (No need to swap if it is already the minimum)
    if (i !== lowest) {
      console.log(`Swap: {arr[i]} <-> {arr[lowest]}`);
      [arr[i], arr[lowest]] = [arr[lowest], arr[i]];
    }
  }
  return arr;
}

selectionSort([34, 22, 10, 19, 17]);

3. Performance Analysis: Is it Better than Bubble Sort?

Let's calculate the Time Complexity of this code.

In conclusion, the Time Complexity itself is O(N^2), same as Bubble Sort, so it is still slow when data increases.

However, in a memory environment where the "Write/Swap" operation is very expensive, Selection Sort can be much more efficient than Bubble Sort.

4. The Fatal Flaw of Selection Sort

Selection Sort has one fatal flaw: it is an Unstable Sort.

When there are duplicate values (e.g., [3, 3]), the 3 that was behind might jump to the front during the sorting process, flipping their original order.

Key Takeaways

We have learned "Sending large numbers to the back (Bubble)" and "Bringing small numbers to the front (Selection)."

However, there is a method we actually use when playing card games. It's the method of picking up one card at a time and "inserting it into the appropriate spot."

Let's meet Insertion Sort, which is the fastest among existing sorting algorithms when data is nearly sorted.

🔗 References