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.
  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:
    radixSort L d : int list -> int -> int list.
    Exempel: radixSort [9821, 5674, 1234, 638] 4 = [638, 1234, 5674, 9821].
  2. 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.
  3. 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.

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: