Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Selection sort — where it appears

A sort that repeatedly scans the unsorted remainder for its smallest element and moves it into place. It makes the same number of comparisons on every input of a given size, and a large majority of them re-establish an order its earlier passes already settled.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

4 bytes32 bytes128 bytes512 bytesrecord:QuicksortMerge sortShellsortHeapsortInsertion sortSelection sortBubble sortQuicksortShellsortMerge sortHeapsortSelection sortInsertion sortBubble sortQuicksortShellsortMerge sortSelection sortHeapsortInsertion sortBubble sortSelection sortQuicksortShellsortMerge sortHeapsortInsertion sortBubble sort1234567n = 512, random input, key 8 bytesa read or a write moves the record; a comparison touches the key

The exchange rate nobody wrote down

Three earlier essays have said in passing that the ranking would change if the elements were large records. None of them computed it. Computed, selection sort goes from second-worst of seven at four bytes a record to best of seven at five hundred and twelve — and the crossover against each rival is a division that takes one line.

counting · Count 0%25%50%75%Merge sort0.0% · 1.03× the floorQuicksort, random pivot0.0% · 1.16× the floorQuicksort, first-element pivot0.0% · 1.18× the floorMerge sort with an insertion cutoff0.0% · 1.31× the floorInsertion sort0.0% · 9.83× the floorShellsort9.8% · 1.31× the floorQuicksort, median-of-three15.4% · 1.18× the floorHeapsort26.2% · 1.45× the floorBubble sort49.2% · 9.83× the floorSelection sort59.9% · 7.77× the floorshare of comparisons whose answer was already implied256 elements, random orderlight: repeats nothing

The questions a sort asks twice

Selection sort makes 32,640 comparisons on 256 elements and 19,561 of them have answers it already holds. Remove every one and it still makes 7.8 times the information floor, because a question can be new and nearly worthless: insertion sort repeats nothing at all and removes 0.72 of a bit per comparison where merge sort removes 0.96. And bubble sort, less its repeats, makes exactly insertion sort's comparisons — at every size.

counting · Count 32641282565121010010³10⁴elements sortedword operations a comparison must cost to break evenSelection sort, pairsSelection sort, closureBubble sort, pairsBubble sort, closureHeapsort, pairsHeapsort, closureQuicksort, median-of-three, pairsQuicksort, median-of-three, closuresolid: pairs asked · dashed: everything impliedrandom input · counted exactly

The price of remembering an answer

Give selection sort a table of the pairs it has already compared and it makes 16,805 comparisons on 256 elements instead of 32,640. The table pays for itself once a comparison costs more than 3.1 word operations, and that price stays near three at every size measured. Give it the full closure of everything its answers imply and it makes 13,079. The closure pays only past 425 operations a comparison at that size, and past 1,659 at twice the size. The cheap memory is worth having on long keys. The complete one is worth having almost nowhere.

counting · Count

Named alongside it

The objects these essays reach for when they reach for this one.

Comparison countCost modelMeasured countPartial orderRedundancyTransitivityBreak-evenBubble sortCounting conventionCrossoverData movementHonest limit

All concepts