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.
  1. 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.
  2. 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.

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: