INDA - Övning 6 våren 2006


Uppgiften ska lämnas till din övningsledare på övningen den 3/3. Glöm inte försättsbladet (pdf) och att alla papper ska häftas samman eller lämnas in i en plastficka.

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 kapitlet om sortering (9.1-9.4) i algoritmboken.


Skriftlig uppgift
Lös uppgift 9.1a-c, 9.2 samt 9.3 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 avbryta rekursionen och byta till insättningssortering. Du kan använda metoden System.currentTimeMillis() för att mäta körtiden hos din algoritm.
Använd gärna testkoden och sorteringsexemplen från förra terminen. Quicksort är ganska klurig att implementera. Var därför extra noga med att skriva bra och utförliga testmetoder. Det underlättar kodning och felsökning.

Gör en experimentell jämförelse av körtiden för insättningssortering och dina tre olika implementationer 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.
  • Rapporten ska innehålla en diskussion där du försöker förstå och förklara dina experimentella resultat.
  • 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.)



Stefan Nilsson
2006-01-24