Jag är ganska bra på att sortera saker. Jag vet t ex att ett väldigt effektivt sätt är:
- Välj ett pivotelement från listan. Med andra ord: välj en stav. Finns lite olika strategier för hur man väljer, men vi kan nöja oss med att ta en slumpmässig stav, första bästa.
- Gå igenom listan stav för stav. Om staven är kortare än pivotstaven, placera den före pivotstaven. Om den är längre: efter pivotstaven.
- Återupprepa och använd denna metod (steg 1-2-3) på stavarna före pivotstaven. Gör sedan samma sak för stavarna efter pivotstaven.
- Iom att man genom steg 3 successivt (det kallas “rekursion”) jobbar med kortare och kortare listor kommer de till sist innehålla bara två eller tre stavar och därför vara sorterade redan i steg 2 och man behöver sålunda inte gå djupare. När man följt alla trådar till sitt slut är hela ursprungslistan i ordning.
Denna metod – algoritm – kallas för Quicksort. Trots att den hittades på redan i datalogins barndom – 1959 – är den fortfarande en av de mer använda för att sortera saker (för datorer dvs). Om man inte har en bra strategi för att välja sitt pivotelement (eller om man bara har väldigt otur när man väljer) kan Quicksort i vissa fall ta onödigt lång tid på sig, men rent generellt hamnar man vanligtvis ganska nära den teoretiska gränsen för hur snabbt det går att sortera en lista.
Killen som hittade på det här heter Tony Hoare – ja det uttalas “whore” – och lever fortfarande. För några år sen var jag på en föreläsning/seminarie med honom. Minns att det var i Birmingham, men minns inte vad han snackade om. Även om han kommit på och gjort några andra häftiga saker så kan det varit så att han snackade om Quicksort. Han är ju trots allt Quicksort-gubben.
Jag är inte så bra på att måla saker. Visste t ex tydligen ingenting om att sprejmåla. Nu vet jag lite mer.