Föreläsningar

Föreläsning 9

Sorteringstekniker

[kapitel 10]
OH-bilder från denna föreläsning

Vad är Divide-and-Conquer?
En teknik för att hitta effektiva algoritmer.

Kan man sortera med Divide-and-Conquer?
Ja, Merge-Sort är ett typexempel.

Hur fungerar Merge-Sort

Hur implementerar man bäst snarlika algoritmer?
Man kan bygga "förlagor", templates, i abstrakta superklasser och sedan fylla i detaljskillnaderna i subklasser.

Hur fungerar Quick-Sort

Hur snabba kan sorteringsalgoritmerna bli?

Finns det metoder som inte bygger på parvisa jämförelser?
T.ex. Bucket-Sort och Radix-Sort.

Kan man räkna ut medianvärden snabbt?
Quick-Select, en slimmad version av Quick-Sort, gör detta.