AD1 -- SML Uppgift 3
Radix-sort användes ursprungligen för att sortera hålkort. Principen
är att man klassificerar 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
klassificeringsmetod: ordningen mellan två likadana tal skall
behållas. Radix-sort beskrivs i CLRS (Introduction to
Algorithms), sidor 170-173 (you need not read up anything
about counting sort, nor use a sorting algorithm to
classify the numbers into the bins). You can choose any
number of bins, corresponding to the base in which your algorithm
views the given numbers, but indicate that base in your specification.
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 i valt basen:
radixSort L d : int list -> int -> int list
så att sorteringstiden för n tal är Θ(n).
Exempel: radixSort [9821, 5674, 7890, 1234,
638] 4 = [638, 1234, 5674, 7890, 9821], assuming the
algorithm has 10 bins, because all the n=5 given numbers
have maximum d=4 digits in base 10. Use d=14 if
viewing those numbers in base 2 and thus using only 2 bins.
- Undersök radix-sort tillsammans med merge-sort eller quick-sort
genom att sortera slumpade listor av 100, 200, ..., 1000 tal. För
att skapa en slumpmässig lista, skriv Random.rangelist
(minimalElement, maximalElement) (numberOfElements,
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 med kurvor. (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 20 februari, klockan 08: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åga 2 ovan, i en *.txt eller *.pdf eller
*.html fil.