Suggest an edit

Improve this article

Refine the answer for “What is selection sort (selection sorts)?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

**Selection sort** is a simple comparison-based algorithm: at each step it finds the minimum (or maximum) element of the unsorted part of the array and swaps it with the first element of that part. It works in-place, requires O(1) extra memory, runs in O(n²) in the best/average/worst cases, and is usually unstable. Pros: simplicity and a minimal number of swaps; cons: slow on large data.

## Detailed breakdown

### Algorithm idea

1. Split the array into two parts: the left one already sorted, the right one still unsorted.
2. Find the index of the minimum element in the right (unsorted) part.
3. Swap that minimum with the first element of the unsorted part.
4. Move the boundary of the sorted part one step to the right and repeat until the end.

### Complexity and properties

- Time: O(n²) in the worst, average, and best cases (always performs ~n(n-1)/2 comparisons).
- Memory: O(1) (in-place).
- Number of swaps: O(n) (the minimum among the simple quadratic sorts).
- Stability: usually unstable (equal elements can swap places). A stable version is possible by shifting elements instead of swapping.
- Adaptivity: not adaptive - even for nearly sorted arrays it performs the same comparisons.

### Pseudocode

```text
for i = 0 to n-2:
  min = i
  for j = i+1 to n-1:
    if A[j] < A[min]:
      min = j
  swap A[i], A[min]
```

### JavaScript example (regular, unstable version)

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

// Example
// console.log(selectionSort([64, 25, 12, 22, 11])); // [11, 12, 22, 25, 64]
```

### Step-by-step example

Array: [64, 25, 12, 22, 11]

```text
Step 1: minimum 11 (index 4) → swap with index 0
[11, 25, 12, 22, 64]
Step 2: minimum among [25, 12, 22, 64] = 12 (index 2) → swap with index 1
[11, 12, 25, 22, 64]
Step 3: minimum among [25, 22, 64] = 22 (index 3) → swap with index 2
[11, 12, 22, 25, 64]
Step 4: minimum among [25, 64] = 25 → no swap needed
[11, 12, 22, 25, 64]
```

### Stable version (shifting instead of swapping)

To make selection sort stable, the found minimum is not swapped in place but "inserted" at position i, shifting a block of elements one position to the right. This preserves the relative order of equal elements at the cost of more assignments.

```js
function stableSelectionSort(arr, compare = (a, b) => a - b) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (compare(arr[j], arr[minIdx]) < 0) {
        minIdx = j;
      }
    }
    const key = arr[minIdx];
    while (minIdx > i) {
      arr[minIdx] = arr[minIdx - 1];
      minIdx--;
    }
    arr[i] = key;
  }
  return arr;
}

// Example
// console.log(stableSelectionSort([3, 2, 2, 1])); // [1, 2, 2, 3] - the original order of the equal "2"s is preserved
```

### When it is appropriate to use

- Teaching and reviewing the basic principles of sorting.
- When a minimal number of swaps/writes is critical (for example, media with expensive write operations).
- Very small arrays, where simplicity matters more than speed (although insertion sort is usually better on nearly sorted data).

### Common interview questions

- Is selection sort stable?
Usually not: swapping the minimum into position i can change the order of equal elements. Stability is achieved by shifting instead of swapping.
- How does it differ from bubble sort and insertion sort?
Bubble sort makes many swaps but can finish early on nearly sorted arrays; selection sort makes few swaps but a fixed number of comparisons (not adaptive). Insertion sort is faster on nearly sorted data but makes more moves; selection sort saves on swaps.
- How many comparisons/swaps does it perform?
Comparisons ≈ n(n-1)/2; swaps no more than n-1 (exactly one per pass when needed).

### Variations

- Selecting the maximum and placing it at the end (an equivalent idea, a pass from the right).
- Two-directional selection sort: in one pass find both the minimum and the maximum and place them in position (roughly halves the number of passes, but is more complex to implement).
- For linked lists: convenient to implement stably by moving nodes instead of swapping values.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts785 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.