Inlämningsuppgift 1 - PK3 VT-03

Inlämningsuppgift 1 skall lämnas in senast söndag 25/5 kl. 24:00. Lämna in den med hjälp av inlämningssystemet i slutet av denna sida. Se till att läsa igenom kodkonventionerna innan du börjar. Dessa skall följas.

Redovisning

Uppgiften skall redovisas på vanligt sätt (med inlämningssystemet, se längst ner på sidan). Programmet skall vara välskrivet och välkommenterat. Dessutom skall det vara provkört och körexempel skall ingå i redovisningen. Ange också var källkoden finns så programmet kan provköras i samband med rättning.

Uppgiften skall lösas och redovisas individuellt. Naturligtvis är det acceptabelt att diskutera problem med varandra - men gör du detta så ange gärna vem du pratat med. Läs etik-reglerna för kursen.

Innan du börjar skriva kod, se till att läsa igenom hela uppgiften.

Allmänt

Radix-sort användes ursprungligen för att sortera hålkort. Man kan jämföra detta med att sortera ett antal tal vilka alla har samma antal siffror. 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. Med detta menas att den inbördes ordningen mellan två likadana tal skall behållas. Radix-sort beskrivs i Introduction to Algorithms sid 170.

Meningen med den här uppgiften är att implementera radix-sort, och undersöka dess effektivitet.

Uppgift

Implementera radix-sort för heltalslistor: radixSort: int list -> int list
Hur förväntar du dig att sorteringstiden skall bero av indata? Förklara eller ge ett matematisk uttryck.
Undersök radix-sort genom att sortera listor med tal vilka alla har samma antal siffror. Sortera talen i stigande ordning, dvs predikatet som ska jämföra heltalen är <-operatorn. (Uppgiften kan utökas till att omfatta tal med olika antal siffror för den som vill.) Endast slumpade listor behöver sorteras. (Se uppgift 2 för exempel på hur du kan slumpa fram en heltalslista.)

Exempeldata
[6342, 2234, 1098, 1750], vilken sorterad ska bli: [1098, 1750, 2234, 6342].
Jämför effektiviteten med någon av list-sorteringsalgoritmerna som användes i uppgift 2.
- Gör mätningar för några olika storlekar på indata (förslagsvis kan du göra på samma sätt som i uppgift 2).
- Redovisa resultatet i ett diagram.
- Stämmer resultaten med vad du förväntade dig?

För att mäta exekveringstiden kan du använda funktionen timeit: ('a -> 'b) -> 'a -> real i filen ranTime.sml.

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.

Din redovisning ska innehålla

Svar och/eller lösningar på frågorna 1-4 ovan och dess eventuella delfrågor.
Redovisa diagrammet (se fråga 4 ovan) genom att ange URL till diagrammet.

Din inlämning ska vara körbar. Dvs det som inte är kod ska vara bortkommenterat! All kod som du använt för att lösa uppgiften ska redovisas och följa kodkonventionerna.

Inlämning

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