Uppgift 2 -- PK2 VT04 -- Uppsala Universitet

Uppgift

listMergeSort: ('a * 'a -> bool) -> 'a list -> 'a list

Du ska undersöka hur sorteringstiden skiljer sig mellan den och en andra implementation av merge-sort och en implementation av insertion-sort. De två andra funktionerna ska du skriva själv.

Den första funktionen

listOptMergeSort: ('a * 'a -> bool) -> 'a list -> 'a list

Den andra funktionen

ArrayInsertionSort: ('a * 'a -> bool) -> 'a array -> 'a array

Tiden för enstaka sorteringar kan mätas med hjälp av funktionen timeIt: ('a -> 'b) -> 'a -> real, som finns i filen ranTime.sml och tar en funktion f och ett argument a och returnerar exekveringstiden för f applicerat på a.

Vid redovisning av uppgiften ska du använda funktionen go: unit -> unit i filen testSort.sml (som inhåller filen ranTime.sml). Funktionen testkör de tre implementationerna på sorterat, omvänt sorterat och slumpmässigt data och genererar nio filer som sedan kan plottas med gnuplot.

Det ni ska sortera är endast heltal, och predikatet som ska jämföra heltalen är < operatorn (skriv op< som första argument till sorteringsfunktionerna).

Uppgiften består av följande moment:

1. Implementera funktionerna listOptMergeSort och arrayInsertionSort. Om du vill testköra på lite större indata kan du generera slumpmässiga (random) listor och arrayer med följande kommandon:

   För att skapa en slumpmässig lista, skriv:

   Random.rangelist (0, 10000) (numOfElms, Random.newgen())

   För att skapa en slumpmässig array, skriv:

   Array.fromList (Random.rangelist (0, 10000) (numOfElms, Random.newgen()))

2. Redovisa resultatet med hjälp av funktionen go: unit -> unit i filen testSort.sml. Funktionen testkör de tre implementationerna på sorterat, omvänt sorterat och slumpmässigt data. Nio filer genereras, till exempel lmsS.txt för listMergeSort på sorterat data, lmsOI.txt för listOptMergeSort på omvänt sorterat data, och aisR.txt för arrayInsertionSort på slumpmässigt data.

   Filen plotta innehåller en serie gnuplot-kommandon som läser de nio filerna och skapar grafer för de tre sorteringsfunktionerna på filen sort.ps. Skriv gnuplot plotta vid Unix-prompten för att skapa grafen ifrån de tre filerna med mätdata.

3. I varje rekursiv algoritm brukar det finnas följande steg: uppdelning (divide), rekursion (conquer), och kombinering (combine). Beskriv med rekursionsformler hur sorteringstiden beror av antalet element som ska sorteras för var och en av de tre funktionerna. Uttryck dessa formler så att kostnaden för de olika stegen framgår. Lös dessa rekursionsformler med hjälp av Master Theorem.
4. Kommentera experimentet och vilka slutsatser man kan dra av det.

Din redovisning ska innehålla

1. Din sorteringsfunktionerna listOptMergeSort och arrayInsertionSort samt funktionen listMergeSort (se punkt 1 ovan).
2. Sökvägar eller URL till en fil med de tre plottarna (se punkt 2 ovan).
3. Matematisk analys för hur sorteringstiden beror av antalet element som ska sorteras för var och en av de tre funktionerna (se punkt 3 ovan).
4. Dina kommentarer till experimentet och vilka slutsatser man kan dra av det (se punkt 4 ovan).

Din inlämning

• Ditt namn och klass.
• Om du löser uppgiften tillsammans med en annan student, ange den andra studentens namn. I så fall ska endast en av er lämna in en lösning, men båda ska meddela namn, klass och labpartner via inlämningssystemet.
• En kort beskrivning (en rad) av vad det är för fil.
• Alla kommentarer och all dokumentation ska vara på engelska.

Din inlämning ska vara körbar. Det som inte är kod ska vara bortkommenterat.

Glöm inte att alla funktioner ska dokumenteras enligt kodkonventionerna (dvs även listMergeSort).

Hämta ett formulär för att lämna in uppgiften genom att fylla i fälten nedan.