Uppgift 3
Radix-sort användes ursprungligen för att sortera hålkort. Principen
är att man sorterar talen först på den minst signifikanta siffran,
sedan den näst minst signifikanta osv. För att detta skall fungera är
det nödvändigt att man använder en stabil sorteringsalgoritm:
ordningen mellan två likadana tal skall behållas. Radix-sort beskrivs
i CLRS (Introduction to
Algorithms), sidor 170-173. Meningen med den här uppgiften är att
implementera radix-sort för listor och undersöka dess effektivitet.
- Implementera radix-sort för sortera i icke avstigande ordning (dvs
predikatet som ska jämföra tal är ≤-operatorn) en lista
L av naturliga tal med maximalt d siffror:
radixSort L d : int list -> int -> int list.
Exempel: radixSort [9821, 5674, 1234, 638] 4
= [638, 1234, 5674, 9821].
- I varje rekursiv algoritm brukar det finnas följande steg:
uppdelning (divide), rekursion (conquer), och
kombinering (combine). Beskriv med rekursionsformler hur
sorteringstiden av din radixSort funktion beror av
antalet element som ska sorteras. Uttryck dessa formler så att
kostnaden för de olika stegen framgår. Lös dessa
rekursionsformler och förklara därigenom hur sorteringstiden av
din radixSort funktion är O(n) för en lista av
n naturliga tal.
- Undersök radix-sort tillsammans med någon av
list-sorteringsalgoritmerna som har presenteras på någon
föreläsning genom att sortera slumpade listor. För att skapa en
slumpmässig lista, skriv Random.rangelist (minElem,
maxElem) (numOfElms, Random.newgen()). När man slumpar fram
listor bör intervallet mellan största och minsta tal vara minst
100 ggr större än antalet tal, annars ökar risken att få många
dubletter i listorna. Många dubletter gör att man undersöker ett
extremfall istället för ett generellt, slumpat fall. För att mäta
exekveringstiden kan du använda funktionen timeIt i filen
ranTime.sml, som
tar en funktion f och ett argument a och
returnerar exekveringstiden för f applicerat på
a.
- Gör mätningar för några olika storlekar på indata och redovisa
resultaten i ett diagram. (Tips: Använda
gnuplot.)
- Stämmer resultaten med vad du förväntade dig? Varför / varför
inte?
Inlämning
Din redovisning, enligt kursens etikregler, måste lämnas in senast måndag
21 februari, klockan 10:14 (på morgonen), med hjälp av inlämningssystemet, och ska
innehålla:
- SML funktionerna för fråga 1 ovan, i en *.sml textfil, körbar
under Moscow ML version 2.01 (det som inte är kod ska vara
bortkommenterat), och dokumenteras, på engelska, enligt kursens kodkonventionerna.
- Svar, på engelska, på frågorna 2-3 ovan, i en *.txt eller *.pdf
eller *.html fil.