Begreper & referanser
Alle nøkkelbegrepene, formlene og referansene fra Sortering i lineær tid og utvalg, samlet på én side. Bruk denne som oppslag når du leser, øver flashcards eller tar quiz.
Begreper
Sentrale begreper fra kapittelet med korte definisjoner.
En sortering som bare bruker sammenligninger mellom elementer for å bestemme rekkefølgen. Bundet nedenfra av .
En modell av en sammenligningssortering der hver indre node er en sammenligning og hvert løv en mulig permutasjon.
En sortering som bevarer den innbyrdes rekkefølgen til elementer med lik nøkkel. Avgjørende for at Radix-Sort virker.
Sorterer heltallsnøkler i et begrenset område ved å telle forekomster. , stabil, men ikke på stedet.
Sorterer flersifrede nøkler siffer for siffer med en stabil sortering, fra minst til mest signifikant.
Fordeler jevnt fordelte nøkler i bøtter, sorterer hver bøtte, og setter dem sammen. Forventet lineær.
Å finne det -te minste elementet i en samling uten å sortere alt.
Et utvalg basert på Quicksort-partisjonering som bare graver videre i den siden som inneholder svaret. Forventet .
Formler
Hver formel: hva den heter, hvordan den ser ut, og hva symbolene betyr.
Nedre grense for sammenligningssortering
Et beslutningstre for en sammenligningssortering har minst løv, og et binærtre med løv har høyde minst .
Høyde av beslutningstreet
Hver permutasjon må svare til minst ett løv, og treets høyde er antall sammenligninger i verste vei. Stirlings formel gir .
Counting-Sort
Med heltallsnøkler i området teller vi forekomster og plasserer direkte. Lineær når , men bruker ekstra plass.
Radix-Sort
Sorterer sifre fra minst til mest signifikant med en stabil sortering (typisk Counting-Sort med base ) per siffer.
Bucket-Sort, forventet
Med nøkler jevnt fordelt over et intervall havner i snitt konstant mange i hver bøtte, så den lokale sorteringen blir billig.
Randomisert utvalg, forventet
Å finne det -te minste elementet krever ikke full sortering: randomisert partisjonering kaster i snitt bort en konstant brøk av elementene per steg.
Læringsmål
Hva du skal kunne etter å ha lest kapittelet.
- 01Bevise den nedre grensen Ω(n lg n) for sammenligningssortering ved hjelp av et beslutningstre med minst n! løv
- 02Forklare hvordan Counting-Sort sorterer heltallsnøkler i Θ(n+k) ved å telle forekomster, og når den lønner seg
- 03Begrunne hvorfor Radix-Sort trenger en stabil siffersortering, og regne ut kjøretiden Θ(d(n+k))
- 04Forklare hvordan Randomized-Select finner det k-te minste elementet i forventet Θ(n) ved å forkaste én side per partisjonering