Henning Christiansen 7/10-2001
Opgave 1 og 2 har h¿jest prioritet; opgave 3 til efterf¿lgende hjemmearbejde.
Afleveringsopgave til DatC: Opgave 1 og 2 (incl. 1.1, 1.2, 2.1 og 2.2) med afleveringsfrist fredag 18. oktober.
Opgave 1
DefinŽr en klasse, som svarer til spillekort, hvor hvert objekt har to attributter, en farve, som er kl¿r, hjerter, spar, eller ruder, og en v¾rdi som er et tal 1..13. Vi skal bruge klassen til at eksperimentere med sortering, sŒ den skal altsŒ v¾re en Comparable klasse, dvs. som skal udstyres med en compareTo metode.
I f¿rste omgang skal compareTo udtrykke f¿lgende ordning:
Skriv en sŒdan klasse for spillekort; skriv et testprogram med et array af spillekort, fyld nogle spillekort i, og afpr¿v den quicksort-version som blev fremvist ved forel¾sningen (filnavn QSort.java; kan hentes via kursets hjemmeside).
Nu har man i forskellige spil kort forskellige opfattelser af, hvilke spillekort som vejer tungere end andre. F.eks. er det ret almindeligt, at Es (svarende til v¾rdi=1) er et vigtigere kort end Konge (v¾rdi = 13). For at kunne modellere dette er vi n¿dt til at have mere end en mŒde at sammenligne kort pŒ, end den ÒstandardordningÓ som er indbygget i l¿sningen pŒ spg. 1.1. For at rŒde bod pŒ det mŒ vi oprette en ÒComparatorÓ. DefinŽr en sŒdan som udtrykker at kortv¾rdi 2 er mindre end 3, som er mindre end .... som er mindre end 12, som er mindre end 13, som er mindre end 1. Og nu vil vi gerne gentage sp¿rgsmŒl 1.1 med den Comparator. Lav en ny version af quicksortmetoden, som tager et ekstra argument som er en Comparator, og arrayet, den fŒr, beh¿ver nu ikke mere bestŒ af Comparables men blot ObjectÕer. Nu kan du afteste metoden.
Vi skal nu eksperimentere med at sortere heltal Ñ vel og m¾rket ved array af typen Òint []Ó og ikke de kluntede ÒInteger []Ó. Som det blev diskuteret ved forel¾sningen kan den generelle quicksort kun arbejde pŒ arrays af ObjectÕer men ikke arrays af heltal.
Lav en ny version af quicksortmetoden som blev fremvist ved forel¾sningen (filnavn QSort.java; kan hentes via kursets hjemmeside), sŒ den sorterer pŒ Òint []Ó, som sammenlignes med de almindelige sammenligningsoperatorer. ImplementŽr og aftest pŒ et lille eksempel.
Nu skal vi til at lave tidsmŒlinger! Metoden java.lang.System.currentTimeMillis() fort¾ller dig hvor lang tid du har brugt siden programmet startede, sŒ hvis du skal finde ud af, hvor lang tid en bestemt beregning tager kan du g¿re sŒdan her:
System.out.println("Calculating...");
long start = System.currentTimeMillis();
BEREGNING;
System.out.println("["+(System.currentTimeMillis()-start)+"]");
I java.util.Random finder du v¾rkt¿j til at generere tilf¾ldige tal som testdata.
Skriv et eller flere testprogrammer som g¿r det muligt at sammenligne faktiske sorteringstider for f¿lgende:
Afpr¿v dem begge pŒ de samme arrayl¾ngder og giv et estimat pŒ hvor meget hurtigere den sidste metode er. Pr¿v med forskellige l¾ngder array, op til hvad din computer kan klare uden at gŒ i kl¿js. Opf¿rer algoritmerne sig som n log n?
Obs: hvis tidsforbruget lige pludselig ikke ser ud til at f¿lge den n log n kurve vi har fra teorien, nŒr man s¾tter n op, men noget der ligner eksponentielt, kan det meget vel skyldes at Javas garbagecollector er vŒgnet til dŒd.
Opgave 3.
I den quicksortversion, som er benyttet overfor, brugtes en v¾rdi for CUTOFF = 10. Ukritisk kopieret efter bogen. Foretag eksperimenter i stil med dem i opgave 2 for at fŒ bestemt optimale CUTOFF v¾rdier for hver af de to versioner, dvs.med ÒComparable []Ó og med Òint []Ó. Hvis der er stor forskel pŒ de to optimale CUTOFF, fors¿g at forklare hvorfor.