Selection Sort: Half the Comparisons, One Swap per Pass, Still Θ(n²)

If selection sort's inner loop starts at i and does half the comparisons, why is it still Theta of n squared?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Trace the first selection-sort pass

Selection sort (the swap-every-time version from the video) runs its first pass on [7, 3, 9, 2, 5, 1, 6]: the element at index 0 is compared with every element after it, and whenever a smaller one turns up the two swap. Work out the list after this first pass only — by hand, or by writing the pass. Assign that list to after.

L = [7, 3, 9, 2, 5, 1, 6]
# the list after the first pass (index 0 settled)
after = ...  # your code here

L = [7, 3, 9, 2, 5, 1, 6]
# the list after the first pass (index 0 settled)
after = ...  # your code here

Python runs in your browser

⌘/Ctrl + Enter runs

is a list of seven numbers

has the smallest element at index 0

matches the list after one swap-every-time pass

←Previous Bubble Sort: Neighbour Swaps, a did_swap Flag, and a Θ(n²) Worst Case Next Merge Sort: Split to Single Elements, Rebuild with a Linear Merge →