|
INDA - Övning 6 våren 2007
Uppgiften ska lämnas till din övningsledare på övningen den 1/3.
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, R-4.12 och C-4.14 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.
Stefan Nilsson
2007-02-13
|