Quicksort
We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Quicksort �r en av de snabbaste sorteringsalgoritmerna. Den bygger p� en enkel id� men �r ganska komplicerad att implementera om man vill f� bra prestanda f�r alla typer av indata. I quicksort v�ljer man f�rst ut ett av elementen p, det s� kallade pivot-elementet, och delar sedan upp vektorn i tv� delar, s� att alla element som �r mindre �n eller lika med p hamnar i den f�rsta delen. Sedan �terst�r bara att sortera de tv� delvektorerna rekursivt.
Med lite tur s� kommer den h�r algoritmen att kunna bli mycket snabb. Om vi antar att partitioneringen kan g�ras p� linj�r tid (vilket l�tt kan uppn�s) och att den alltid delar upp vektorn i tv� precis lika stora delar (vilket �r h�gst osannolikt) s� blir rekursionsekvationen f�r tiden T(n) att sortera en vektor med n element
F�r att uppn� detta m�ste man dock v�lja pivot-elementet p med st�rre omsorg �n i exemplet ovan. Det kanske mest naturliga valet �r att l�ta p vara medianen av elementen i v[first..last]. N�rmre mitten �n s� kan man ju inte komma. Det g�r att ber�kna medianen p� linj�r tid, men algoritmerna �r s� komplicerade att man tappar alltf�r mycket prestanda. Men situationen �r mer komplicerad �n s�. Vi kan f� problem �ven om vi delar upp elementen runt medianen. Om samtliga tal i v[first..last] �r lika s� kommer partitioneringen att helt misslyckas: alla element �r ju d� lika med pivot-elementet. PivotelementAtt v�lja ett l�mpligt pivot-element p �r en balansakt. Om vi l�gger ned alltf�r lite arbete, som i exemplet ovan d�r vi s�tter p = v[first], s� riskerar vi att f� en v�ldigt skev partitionering. Om vi i st�llet l�gger ner f�r mycket arbete, genom att till exempel ber�kna medianen, s� kan partitioneringen bli b�ttre men alltf�r l�ngsam. Den kanske enklaste l�sningen �r att l�ta pivot-elementet vara ett slumpm�ssigt valt tal ur v[first..last]. Det f�rv�ntade antalet j�mf�relser f�r att sortera en vektor d�r alla element �r olika blir d� 1.39nlog(n). Ett val av pivot-element som man ofta ser �r p = median(v[first], v[first + (last-first)/2], v[last]).Man hoppas d� att �tminstone ett av dessa tre tal ska ligga n�ra mitten och argumenterar att detta kommer att g�lla f�r alla "rimliga" former av indata. Min erfarenhet �r att detta inte alltid st�mmer. Om man v�ljer pivot-element p� detta s�tt och anv�nder partitioneringsalgoritmen i n�sta avsnitt s� f�r man till exempel v�ldigt d�liga resultat n�r indata best�r av en redan sorterad vektor. En mer robust l�sning �r att kombinera b�da id�erna och v�lja pivot-elementet som medianen av tre slumpm�ssigt valda element. PartitioneringF�r att undvika att partitioneringen blir skev om man har m�nga dubbletter i vektorn s� kan man i st�llet dela upp talen i tre grupper: de som �r mindre �n p, de som �r lika med p och de som �r st�rre �n p. Om man placerar alla element som �r lika med pivot-elementet i mitten s� beh�ver man bara sortera de andra tv� delarna. Med hj�lp av en l�mpligt vald loop-invariant f�r vi ordning p� den ganska komplicerade koden.
Man ser l�tt att tidskomplexitet �r linj�r: varje varv i slingan tar konstant tid och avst�ndet mellan mid och high krymper i varje varv, antingen genom att mid blir st�rre eller att high blir mindre. Det g�r att optimera partitioneringskoden ytterligare, men d� p� bekostnad av l�sbarhet och enkelhet. KombinationsalgoritmerErfarenheten visar att quicksort �r den snabbaste j�mf�relsebaserade sorteringsalgoritmen f�r m�nga typer av indata. Ibland finns det dock enklare och snabbare alternativ. Ins�ttningssortering, som visserligen har kvadratisk v�rstafallstid, �r till exempel snabbare f�r sm� sorteringsproblem. I st�llet f�r att v�lja antingen quicksort eller ins�ttningssortering s� kan man med f�rdel kombinera algoritmerna: anv�nd quicksort f�r att sortera delvektorer v[first..last] med m�nga element och ins�ttningssortering om antalet element �r litet. Brytpunkten beror p� m�nga faktorer (hur koden �r skriven, hur indata ser ut, maskinens prestanda) och m�ste d�rf�r provas ut experimentellt. Lyckligtvis visar det sig ofta att valet inte �r s� kritiskt; brytpunkter mellan 10 och 100 brukar fungera bra. |