Selection Sort

Question 1

How many swaps does Selection Sort perform in the worst case?

Accepted Answer

O(n) — Selection Sort performs exactly n-1 swaps (one per pass), making it efficient when swap cost is high.

Question 2

What is selection sort's time complexity in ALL cases (best, average, worst)?

Accepted Answer

O(n²) in every case — Selection sort always scans the remaining unsorted region to find the minimum, regardless of input order, so it is Θ(n²) in best, average, and worst cases — it is not adaptive.

Question 3

How many SWAPS does selection sort perform in the worst case?

Accepted Answer

At most n−1 — Each outer iteration places one element via a single swap, so at most n−1 swaps total — its key advantage when writes are expensive (e.g. flash memory).

Question 4

Selection sort works by, on each pass…

Accepted Answer

Selecting min, place at front — It finds the smallest remaining element and swaps it into the next sorted position, growing a sorted prefix one element per pass.

Question 5

Is the standard array-based selection sort stable?

Accepted Answer

No, the long swap reorders equals — Swapping the minimum into place can jump an equal element past another, breaking relative order. A stable variant exists but uses shifting/insertion instead of swapping.

Question 6

Selection sort's auxiliary space complexity is…

Accepted Answer

O(1) — It sorts in place with only a constant amount of extra storage (index of the current minimum).

Question 7

How many COMPARISONS does selection sort make on n elements?

Accepted Answer

n(n−1)/2 comparisons total — Finding each minimum scans the shrinking unsorted region: (n−1)+(n−2)+…+1 = n(n−1)/2 comparisons, always — even if already sorted.

Question 8

Why is selection sort sometimes preferred over bubble sort despite both being O(n²)?

Accepted Answer

It minimizes writes/swaps — When writing to memory is costly (e.g. EEPROM/flash with limited write cycles), selection sort's ≤ n−1 swaps beat bubble sort's potentially O(n²) swaps.

Question 9

On an already-sorted array, selection sort performs…

Accepted Answer

Still O(n²) comparisons — It cannot detect sortedness; it still scans the entire unsorted region each pass to confirm the minimum, costing Θ(n²).

Question 10

After i passes of selection sort (ascending), what holds?

Accepted Answer

First i are smallest, placed — The sorted prefix grows from the front: after i passes the first i positions hold the i smallest elements in order.

One pass of selection sort

Test your knowledge

How many swaps does Selection Sort perform in the worst case?

The short version

In more depth

How It Works

Key Properties

When to reach for this

Interview Questions

References & Further Reading

Related topics

Love this visualization?