Algoritmer og datastrukturerHjem

CMD + K

Tilbake til Algoritmer og datastrukturer

TDT4120 · Algoritmer

Sortering, steg for steg

Kjør seks klassiske algoritmer på det samme arrayet. Følg hver sammenligning og hvert bytte i pseudokoden — og se hvilke celler hver av dem leser i minnet.

Elementer
12 elementer · søylehøyde = verdi
SammenlignerPivotSortert
34
12
58
7
41
25
63
18
49
30
9
53
1 / 110Start — boblesortering.
Hjelpe-minne0 register i brukO(1)
·

Sorterer på stedet: ett enkelt register holder verdien den jobber med nå — nøkkelen, det løpende minimumet, eller en verdi midt i et bytte.

Lær mer

Alle seks løser samme oppgave, men med ulik kostnad. De kvadratiske (bubble, insertion, selection) er enkle og sorterer på stedet i O(1) ekstra minne, men bruker O(n²) sammenligninger.

De O(n log n)-baserte er raskere: merge sort er stabil og garantert O(n log n), men trenger en O(n) buffer; heapsort er på stedet og garantert O(n log n); quicksort er raskest i praksis, men kan falle til O(n²) på en uheldig pivot.

Hjelpe-minne-panelet under søylene viser nettopp denne forskjellen: ett register for de kvadratiske, en buffer på n celler for merge, og en rekursjons-stack med dybde ≈ log n for quicksort.

Relaterte kapitler

1Algoritmer, kjøretid og asymptotisk notasjon3Splitt og hersk5Hauger og binære søketrær