Speed:

Selection Sort

Time: O(n²)Space: O(1)Not Stable

🎯How Selection Sort Works

Selection Sort works by repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning. The algorithm divides the array into two parts: a sorted portion (initially empty) and an unsorted portion.

The algorithm follows these steps:

Find minimum: Search for the smallest element in the unsorted portion
Swap: Exchange it with the first element of the unsorted portion
Expand sorted region: Move the boundary between sorted and unsorted portions
Repeat: Continue until the entire array is sorted

💻Implementation

function selectionSort(arr) {
  let n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }

    // Swap the found minimum element with the first element
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  return arr;
}

📊Algorithm Analysis

Time Complexity

• Best: O(n²) - even if already sorted
• Average: O(n²)
• Worst: O(n²) - reverse sorted
• Comparisons: Always (n-1) + (n-2) + ... + 1

Key Properties

• Not stable: relative order not preserved
• In-place: requires only O(1) extra memory
• Not adaptive: always performs O(n²) comparisons
• Minimum swaps: at most n-1 swaps

🏆 Advantages

• Simple to understand and implement
• Minimum number of swaps (at most n-1)
• In-place sorting - no extra memory needed
• Performance independent of input order
• Good for small datasets

⚠️ Disadvantages

• O(n²) time complexity in all cases
• Not stable - changes relative order
• Not adaptive - doesn't benefit from partial sorting
• Poor performance on large datasets
• More comparisons than insertion sort