Selection Sort

A simple comparison-based algorithm that finds the minimum element in each pass and places it at the beginning. Easy to understand but inefficient for large datasets.

Controls

Array Size

Speed: 1000ms

Statistics

Current Pass:0

Total Passes:-1

Comparisons:0

Swaps:0

Array Size:0

Complexity

Time Complexity:

All Cases:O(n²)

Space Complexity:

O(1)In-place sorting

Properties:

Unstable

In-place

Not adaptive

Array Visualization

Pass 0/-1 - Ready

Unsorted

Current Minimum

Comparing

Selected Position

Sorted

How Selection Sort Works:

Algorithm Steps:

Find minimum element in unsorted portion
Swap it with first unsorted element
Move boundary of sorted region
Repeat until entire array is sorted

Key Properties:

O(n²) comparisons: Always (n-1) + (n-2) + ... + 1
O(n) swaps: At most one swap per pass
Not adaptive: Same time regardless of input
Unstable: May change relative order

Implementation

Selection Sort Implementation

function selectionSort(arr) {
  const n = arr.length;
  
  // One by one move boundary of unsorted subarray
  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
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  
  return arr;
}

// Time Complexity: O(n²) - always
// Space Complexity: O(1) - in-place
// Comparisons: n(n-1)/2
// Swaps: O(n) - at most n-1 swaps

Optimized Version

function selectionSortOptimized(arr) {
  let n = arr.length;
  
  for (let i = 0; i < Math.floor(n / 2); i++) {
    let minIndex = i;
    let maxIndex = i;
    
    // Find both min and max in one pass
    for (let j = i + 1; j < n - i; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
      if (arr[j] > arr[maxIndex]) {
        maxIndex = j;
      }
    }
    
    // Place minimum at start
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    
    // Adjust maxIndex if it was at position i
    if (maxIndex === i) {
      maxIndex = minIndex;
    }
    
    // Place maximum at end
    [arr[n - 1 - i], arr[maxIndex]] = [arr[maxIndex], arr[n - 1 - i]];
  }
  
  return arr;
}

Generic Implementation

function selectionSort(arr, compareFn) {
  const compare = compareFn || ((a, b) => a - b);
  const n = arr.length;
  
  for (let i = 0; i < n - 1; i++) {
    let extremeIndex = i;
    
    for (let j = i + 1; j < n; j++) {
      if (compare(arr[j], arr[extremeIndex]) < 0) {
        extremeIndex = j;
      }
    }
    
    if (extremeIndex !== i) {
      [arr[i], arr[extremeIndex]] = [arr[extremeIndex], arr[i]];
    }
  }
  
  return arr;
}

// Usage examples:
// selectionSort([3, 1, 4, 1, 5]); // ascending
// selectionSort([3, 1, 4, 1, 5], (a, b) => b - a); // descending
// selectionSort(objects, (a, b) => a.name.localeCompare(b.name));

Performance Analysis

Time Complexity - O(n²)

Always performs n(n-1)/2 comparisons regardless of input order. No best or worst case - always quadratic.

• Comparisons: n(n-1)/2

• Swaps: 0 to n-1

• Passes: n-1

Space Complexity - O(1)

In-place sorting algorithm using only a constant amount of additional memory space.

• No additional arrays

• Only loop variables

• Memory efficient

When to Use

Best for small datasets or when memory is limited. Minimizes number of swaps.

• Small arrays (< 20 elements)

• Memory-constrained environments

• When swaps are expensive

Comparison with Other O(n²) Sorts

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

Previous: Merge Sort Next: Insertion Sort