Uppgift 6 våren 2011Uppgiften ska lämnas till din övningsledare på övningen den 25/2. Börja 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. HemuppgiftLäs den här texten om quicksort. Skriftlig uppgiftTidsmätning i JavaKlassen Stopwatch implementerar ett enkelt stoppur. Som du ser i TimingExample så är det lätt att mäta tiden det tar att exekvera ett kodavsnitt, men resultaten kan variera kraftigt mellan körningar. Tänk ut och beskriv en bra strategi för tidsmätning i Java.
QuicksortDu ska implementera några varianter av quicksort i Java och mäta deras hastighet. Din algoritm ska sortera en vektor av heltal (int) och du ska testa följande varianter av algoritmen:
Glöm inte att testa alla fyra kombinationer: med och utan slumpmässigt pivot-element, samt med och utan insättningssortering. Tag dessutom med Javas egen sorteringsalgoritm Arrays.sort(int[]) i dina experiment. Quicksort är ganska klurig att implementera. Var därför noga med att skriva bra och utförliga tester. Det underlättar kodning och felsökning. Återanvänd gärna testkoden och implementationen av insättningssortering från förra terminen. Du ska testa att sortera vektorer av olika storlek (t.ex. från 1.000 till 1.000.000 element) och olika typer av data. Följande måste vara med
ImplementationstipsI den här uppgiften ska du göra upprepade tester och mätningar på olika varianter av samma algoritm. För att slippa kodupprepning kan du med fördel definiera ett gränssnitt som beskriver en metod som sorterar en vektor av heltal. Till exempel så här:
Om du skriver dina sorteringsalgoritmer i klasser som implementerar IntSorter så kan du sedan lätt skriva test- och mätkod som arbetar på sådana objekt. Det kan också vara praktiskt att representera indata med hjälp av en klass. Eftersom den här uppgiften är ganska stor så har jag gjort en del av jobbet. Klassen Data.java kan skapa alla typer av indata som behövs i uppgiften. Tag gärna en titt på main-metoden. Den innehåller exempel på hur man kan använda klassen. Med hjälp av de här två datatyperna är det lätt att skriva en generell mätmetod. Till exempel så här:
|