Föreläsning 15: Enkel sortering

Urvalssortering (Selection sort)

Vi tänker oss att vi ska sortera en vektor med N tal. Totalt krävs N(N-1)/2 jämförelser och N-1 byten, helt oberoende av hur pass osorterad vektorn är från början. Tiden är alltså i stort sett proportionell mot kvadraten på N. Man säger att komplexiteten är O(N^2).

Bubbelsortering (Bubble sort)

En något smartare metod än urvalssortering är denna: Totalt krävs i värsta fall N(N-1)/2 jämförelser och lika många byten. Men om vektorn är nästan sorterad från början räcker det med några få genomgångar, och då blir bubbel snabbare är urval.

Insättningssortering (Insertion sort)

Bäst av dom enkla metoderna är insättning. Den känns särskilt naturlig om man hämtar talen ett efter ett från en fil och sorterar in dom i en vektor. Insättning fungerar också om talen finns i vektorn från början. Efter k insättningar är vektorsegmentet v[1]...v[k] ordnat och v[k+1] är det nya talet som ska sättas in.

Komplexiteten är i allmänhet O(N^2) men om vektorn är nästan sorterad från början är insättning den snabbaste algoritmen.


^ Upp till kurssidan.


Sidansvarig: <vahid@nada.kth.se>
Senast ändrad 30 september 2003
Tekniskt stöd: <webmaster@nada.kth.se>