AV
LibrarySelection Sort

Selection Sort

Easy

Selection Sort is a simple sorting algorithm that divides the input list into two parts: sorted and unsorted. It repeatedly finds the minimum element from the unsorted part and places it at the beginning.

Time Complexity

O(n²)

Space Complexity

O(1)

Category

Sorting

Introduction to Selection Sort

Selection Sort is a straightforward sorting algorithm that divides the input array into two regions: sorted and unsorted. It works by repeatedly finding the minimum element from the unsorted region and moving it to the sorted region.

How It Works

The algorithm operates by maintaining a boundary between sorted and unsorted portions:

1. Start with the entire array as unsorted

2. Find the minimum element in the unsorted portion

3. Swap it with the first element of the unsorted portion

4. Move the boundary one position to the right

5. Repeat until the entire array is sorted

Algorithm Complexity

**Time Complexity**: O(n²) - We perform (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons
**Space Complexity**: O(1) - Only requires a constant amount of additional space

Best and Worst Cases

**Best Case**: O(n²) - Even when array is sorted, we still make comparisons
**Worst Case**: O(n²) - When the array is reverse sorted
**Average Case**: O(n²) - For random data

Advantages

1. Simple and easy to understand

2. In-place sorting (minimal extra memory)

3. Performs well on small datasets

4. Guaranteed number of comparisons: n(n-1)/2

5. Useful when memory write is expensive

Disadvantages

1. Unstable sorting (doesn't preserve relative order of equal elements)

2. O(n²) time complexity is inefficient for large datasets

3. No optimization possible (always performs the same comparisons)

4. Not adaptive to existing order in the data

When to Use

**Small arrays**: Efficient for arrays with fewer than 50 elements
**Memory-constrained systems**: When you need minimal extra space
**Write minimization**: When memory writes are expensive (flash memory)
**Nearly sorted data**: Actually no better than random data

Comparison with Bubble Sort

Selection Sort does fewer swaps than Bubble Sort
Both have O(n²) time complexity
Selection Sort is more predictable
Bubble Sort is more adaptive with optimization

Real-world Applications

Sorting small collections
Educational demonstrations
Systems where memory writes are costly
Situations requiring deterministic behavior

Key Takeaways

  • Divides list into sorted and unsorted
  • Finds minimum element repeatedly
  • Non-adaptive sorting
  • In-place sorting
  • Unstable sorting algorithm
  • Good for small datasets

Implementation

function selectionSort(arr) {
  const 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;
      }
    }
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
  }
  return arr;
}

Tags

sortingcomparisonsimplebeginner

Quick Stats

Difficulty:Easy
Type:Sorting

Share