Selection Sort

A simple sorting algorithm that repeatedly finds the minimum element from the unsorted portion and places it at the beginning.

Algorithm Information

Time Complexity

Best: O(n²)

Average: O(n²)

Worst: O(n²)

Space Complexity

O(1)

Properties

• Unstable sorting algorithm

• In-place sorting

• Minimum number of swaps

• Simple implementation

1/49

Speed: 1x

Algorithm Code

1function selectionSort(arr) {
2  const n = arr.length;
3  
4  for (let i = 0; i < n - 1; i++) {
5    // Find the minimum element in remaining array
6    let minIndex = i;
7    
8    for (let j = i + 1; j < n; j++) {
9      if (arr[j] < arr[minIndex]) {
10        minIndex = j;
11      }
12    }
13    
14    // Swap the found minimum element with first element
15    if (minIndex !== i) {
16      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
17    }
18  }
19  
20  return arr;
21}

Variable State

i:0

j:1

n:7

minIndex:0

Array Visualization

Watch how Selection Sort finds the minimum element in each pass and places it in the correct position

640

341

252

123

224

115

906

Statistics

Comparisons0

Swaps0

Step1 / 49

Legend

Comparing / Current Minimum

Swapping Elements

Sorted (Final Position)

Unsorted

Starting Selection Sort algorithm

How Selection Sort Works

Learn the fundamentals of selection-based sorting through systematic minimum-finding and position-swapping.

Algorithm Overview

Selection Sort works by repeatedly finding the minimum element from the unsorted portion of the array and placing it at the beginning of the sorted portion. It maintains two subarrays: a sorted subarray at the beginning and an unsorted subarray for the rest.

🔍 Selection Strategy

The algorithm "selects" the smallest element from the unsorted portion in each iteration. Unlike bubble sort which moves elements gradually, selection sort places each element directly in its final position with a single swap per iteration, making it more efficient in terms of writes.

Step-by-Step Process

Find Minimum

Start from the first unsorted position and scan through the entire unsorted portion to find the index of the minimum element.

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

Swap Elements

Swap the found minimum element with the first element of the unsorted portion. This places the minimum in its correct final position.

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

Expand Sorted Portion

The sorted portion now includes one more element. Move the boundary between sorted and unsorted portions one position to the right.

Key Insight: Each iteration places exactly one element in its final sorted position!

Repeat Until Complete

Continue this process for n-1 iterations. After n-1 iterations, the last element is automatically in its correct position.

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

}

Selection Sort in Action

Here's how selection sort processes an example array:

Initial: [64, 25, 12, 22, 11] - Sorted: [], Unsorted: [64, 25, 12, 22, 11]

Pass 1: Find min(64,25,12,22,11) = 11 → [11, 25, 12, 22, 64]

Pass 2: Find min(25,12,22,64) = 12 → [11, 12, 25, 22, 64]

Pass 3: Find min(25,22,64) = 22 → [11, 12, 22, 25, 64]

Pass 4: Find min(25,64) = 25 → [11, 12, 22, 25, 64]

Final: [11, 12, 22, 25, 64] - Last element automatically sorted

🔄 Invariant Property

At the start of iteration i, elements at positions [0...i-1] are in their final sorted positions and are smaller than all elements in positions [i...n-1]. This invariant ensures correctness.

Complete Implementation

Here's the complete selection sort implementation with detailed comments:

function selectionSort(arr) {
    const n = arr.length;
    
    // Traverse through all array elements
    for (let i = 0; i < n - 1; i++) {
        // Find the minimum element in remaining unsorted array
        let minIndex = i;
        
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // Swap the found minimum element with the first element
        // Only swap if minimum is not already at position i
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
        
        // Now arr[0...i] is sorted and contains the i+1 smallest elements
    }
    
    return arr;
}

// Optimized version that tracks if any swaps were made
function selectionSortOptimized(arr) {
    const n = arr.length;
    let swaps = 0;
    
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i;
        
        // Find minimum in unsorted portion
        for (let j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // Swap only if necessary
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
            swaps++;
        }
    }
    
    console.log(`Selection sort completed with ${swaps} swaps`);
    return arr;
}

// Example usage:
const numbers = [64, 34, 25, 12, 22, 11, 90];
console.log("Original:", numbers);
selectionSort(numbers);
console.log("Sorted:", numbers);

Key Concepts & Characteristics

✅ Advantages

•Simple implementation: Easy to understand and code
•Minimal swaps: At most n-1 swaps, good for expensive write operations
•In-place sorting: Only requires O(1) extra memory
•Consistent performance: Always O(n²) comparisons regardless of input
•No additional data structures: Works directly on the input array

❌ Disadvantages

•Poor time complexity: O(n²) in all cases
•Not stable: Equal elements may change relative order
•Not adaptive: Doesn't benefit from partially sorted data
•Many comparisons: Always performs n(n-1)/2 comparisons
•Poor cache performance: Non-sequential access patterns

⚖️ Write-Optimized Algorithm

Selection sort performs at most n-1 swaps, making it useful when write operations are expensive (e.g., writing to flash memory, moving large objects). While it makes many comparisons, it minimizes the number of actual data movements compared to other O(n²) algorithms.

Complexity Analysis

Best Case

O(n²)

Even with sorted input, algorithm still searches for minimum in each iteration.

Average Case

O(n²)

Random data still requires the same number of comparisons to find minimums.

Worst Case

O(n²)

Reverse sorted array requires maximum swaps but same number of comparisons.

Mathematical Analysis

Comparisons: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)

Swaps (Best): 0 swaps (already sorted)

Swaps (Average): ~n/2 swaps

Swaps (Worst): n-1 swaps (maximum possible)

Space Complexity: O(1) - Only uses constant extra space

Why Selection Sort is Unstable

Selection sort is unstable because it can change the relative order of equal elements:

Example: [4a, 2, 4b, 1] (where 4a and 4b are equal but distinguishable)

Step 1: Find min(4a,2,4b,1) = 1 → [1, 2, 4b, 4a] (swap 4a with 1)

Result: 4b now comes before 4a, violating stability

🔄 Making Selection Sort Stable

Selection sort can be made stable by shifting elements instead of swapping, but this increases the number of writes from O(n) to O(n²), eliminating its main advantage. The stable version would shift all elements between the minimum and current position.

When to Use Selection Sort

✅ Good for:

• Small datasets: Simple implementation for arrays < 20 elements
• Expensive writes: When swapping/moving data is costly
• Memory constraints: Minimal memory overhead required
• Educational purposes: Teaching sorting algorithm concepts
• Embedded systems: Simple, predictable behavior
• Finding k smallest: Can stop after k iterations

❌ Avoid for:

• Large datasets: O(n²) becomes prohibitively slow
• Stability required: Use stable sorting algorithms
• Performance-critical applications: Much better alternatives exist
• Nearly sorted data: Doesn't take advantage of existing order
• Real-time systems: Predictable but slow performance

🎯 Specialized Use Case

Selection sort is particularly useful for finding the k smallest elementswithout fully sorting the array. You can stop after k iterations, giving you the k smallest elements in sorted order at the beginning of the array in O(k×n) time.

Selection Sort vs Other O(n²) Algorithms

Algorithm	Comparisons	Swaps	Stable	Adaptive
Selection Sort	O(n²) always	O(n) max	❌	❌
Bubble Sort	O(n) to O(n²)	O(n²) max	✅	✅
Insertion Sort	O(n) to O(n²)	O(n²) max	✅	✅

Selection sort's main advantage is its minimal number of swaps, making it suitable when write operations are more expensive than read operations.