Selection Sort

Finding the minimum in each pass

Selection sort is an in-place comparison-based sorting algorithm. It divides the input list into two parts: a sorted sublist of items which is built up from left to right, and a sublist of the remaining unsorted items. In each step, the smallest element is "selected" from the unsorted sublist and swapped with the leftmost unsorted element.

Current Pass

0 / 0

Comparisons

Swaps

Press "Start Sorting" to begin

Unsorted

Comparing

Current Min

Sorted

Speed

Algorithm Theory

Selection sorting excels in its simplicity and the fact that it performs the minimum number of swaps ($O(n)$) compared to other simple algorithms like Bubble Sort. It is an "in-place" algorithm, meaning it doesn't require extra storage regardless of the input size.

One Swap Rule

In each pass, Selection Sort finds the absolute minimum element from the unsorted part and performs exactly one swap to place it in its final sorted position.

Inefficiency

Its main drawback is that it always takes $O(n^2)$ time, even if the array is already sorted, because it must scan the remaining elements to "confirm" the minimum.

Detailed Stats

Time Complexity$O(n^2)$

Best Case$O(n^2)$

Space Complexity$O(1)$

StabilityUnstable

Code Preview

Pseudocode

JavaScript

1for (let i = 0; i < n; i++) {
2  let min = i;
3  for (let j = i + 1; j < n; j++) {
4    if (arr[j] < arr[min]) min = j;
5  }
6  if (min !== i) swap(arr, i, min);
7}

Pro Tip

Use Selection Sort when memory writes are costly (e.g., writing to Flash memory), as it minimizes swaps.

Implementations

Python Implementation

Pseudocode

Python

1def selection_sort(arr):
2    n = len(arr)
3    for i in range(n):
4        # Find the minimum element in remaining 
5        # unsorted array
6        min_idx = i
7        for j in range(i + 1, n):
8            if arr[j] < arr[min_idx]:
9                min_idx = j
10                
11        # Swap the found minimum element with 
12        # the first element        
13        arr[i], arr[min_idx] = arr[min_idx], arr[i]
14    return arr

JavaScript Implementation

Pseudocode

JavaScript

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

Algorithm Theory

One Swap Rule

In each pass, Selection Sort finds the absolute minimum element from the unsorted part and performs exactly one swap to place it in its final sorted position.

Inefficiency

Its main drawback is that it always takes $O(n^2)$ time, even if the array is already sorted, because it must scan the remaining elements to "confirm" the minimum.

Implementations

Python Implementation

Pseudocode

Python

1def selection_sort(arr):
2    n = len(arr)
3    for i in range(n):
4        # Find the minimum element in remaining 
5        # unsorted array
6        min_idx = i
7        for j in range(i + 1, n):
8            if arr[j] < arr[min_idx]:
9                min_idx = j
10                
11        # Swap the found minimum element with 
12        # the first element        
13        arr[i], arr[min_idx] = arr[min_idx], arr[i]
14    return arr

JavaScript Implementation

Pseudocode

JavaScript

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