Uppgift 6 våren 2008

Uppgiften ska lämnas till din övningsledare på övningen den 27,29/2. Glöm inte försättsbladet (pdf) och att alla papper ska häftas samman eller lämnas in i en plastficka. Jag rekommenderar att du börjar i god tid.

För godkänt måste du ha gjort samtliga deluppgifter. Det är tillåtet att göra enstaka fel och misstag men det är viktigt att du försöker lösa samtliga uppgifter. Om du kör fast med någon uppgift så finns det som vanligt hjälp att få på labbarna.

Hemuppgift

Studera avsnitten om sortering (4.1, 4.3-4.5, 4.8) i algoritmboken.

Skriftlig uppgift

Lös uppgift R-4.9, R-4.10 och R-4.12 i algoritmboken.

Implementera quicksort i Java. Din algoritm ska sortera en vektor av heltal (int[]). Gör tre varianter av algoritmen.

• En variant där pivot-elementet väljs slumpmässigt med hjälp av Javas slumptalsgenerator;
• en variant där pivot-elementet väljs som medianen av det första, det mittersta och sista elementet i vektorn;
• samt en variant där korta delvektorer sorteras med insättningssortering.

Testa experimentellt när det är lämpligt att byta till insättningssortering. Du kan använda metoden System.currentTimeMillis() för att mäta körtiden hos dina algoritmer.

Quicksort är ganska klurig att implementera. Var därför noga med att skriva bra och utförliga testmetoder. Det underlättar kodning och felsökning. Återanvänd gärna testkoden och implementationen av insättningssortering från uppgift 8 förra terminen.

Du ska göra en experimentell jämförelse av körtiden för fyra olika algoritmer: insättningssortering samt de tre olika implementationerna av quicksort. Du ska testa att sortera vektorer av olika storlek (t.ex. 100, 1.000, 10.000, 100.000 och 1.000.000 element) och olika typer av data (t.ex. slumpmässiga tal, redan sorterade tal, baklänges sorterade tal).

Resultaten av dina experiment ska presenteras i en kort rapport.

• Det ska framgå tydligt vilka tester du har gjort och vilka testdata du har använt.
• Resultaten ska presenteras på ett överskådligt sätt, till exempel i diagramform. Tänk på att läsaren (dvs din övningsledare) snabbt ska kunna se vilka experiment du har gjort och vilka resultat du har kommit fram till. Man ska inte behöva läsa din kod för att förstå. (Däremot ska du som vanligt lämna in en utskrift av koden.)
• Rapporten ska innehålla en diskussion där du försöker förstå och förklara dina experimentella resultat.