Laboration 1: Tidtagning av sorteringsalgoritmer

Målsättning

Målet med denna laboration är att du ska få en känsla för hur väl de teoretiska modellerna om asymptotisk komplexitet stämmer med den verkliga körtiden för ett program.

Du ska lära dig

Uppgift

Du ska implementera en enkel sorteringsalgoritm (bubbelsortering) och jämföra dess prestanda med en metod som finns färdig i Java (java.util.Arrays.sort). Som testdata finns filen /info/grudat00/labbar/osorterad som innehåller 121276 ord i slumpmässig ordning.

Ditt program behöver inte använda sig av något grafiskt användargränssnitt och skrivs därför enklast som en s.k. application. Du ska dela upp programmet, med hjälp av klasser och metoder, så att själva sorteringsalgoritmen inte är beroende av den faktiska lagringen och typen av element. Detta innebär att själva sorteringsmetoden ska anropa generella metoder för jämförelser och flyttning av element.

Använd ditt program för att mäta hur lång tid det tar att sortera olika stora ordlistor, förslagsvis 10-20 mätvärden. Gör ett diagram där du samtidigt visar två kurvor: dina mätta tider samt den teoretiska tillväxttakten (anpassad med en lämplig skalningskonstant). Du kan förslagsvis använda GnuPlot eller Matlab för att rita diagrammen. Gör en skattning av hur lång tid det borde ta att sortera alla 121276 orden.

Upprepa experimentet ovan med den inbyggda metoden sort som finns i klassen java.util.Arrays. Denna metod kräver att orden ligger lagrade i en vektor. Du kan därför inte använda samma gränssnitt mot datalagringen som du gjorde för bubbelsorteringen.

Redovisning

Denna laboration redovisas i form av en skriftlig labbrapport. Labbrapporten skall innehålla följande:

Tips inför genomförandet

Den första deluppgiften du måste ta hand om är att läsa in ordlistan i programmet och lagra den i en lämplig datastruktur. Eftersom filen innehåller ett ord per rad är det lämpligt att utnyttja metoden readline() som finns i klassen BufferedReader. Ett problem vid inläsningen är att du inte i förväg vet hur många ord ordlistan innehåller. En snygg lösning på detta är att utnyttja någon av de färdiga abstrakta lagringsstrukturerna för sekvenser som finns i paketet java.util, t.ex. ArrayList. När alla orden väl är inlästa är det sedan enkelt att flytta över dem till en String-vektor el.dyl. vid behov.

Tidmätningen gör man enklast genom att anropa metoden System.currentTimeMillis() före och efter den algoritm man vill mäta på. Tänk på att det är bara själva sorteringen man vill mäta tiden för, inte t.ex. inläsningen av alla orden från fil och liknande.

Du ska ju mäta körtiden som en funktion av antalet ord som ska sorteras. För att få kortare ordlistor kan du låta programmet läsa in ett begränsat antal ord. Ett annat alternativ är att utnyttja Unix-verktyg för att klippa bort ett visst antal rader ur en fil (t.ex. programmen head eller tail).

Grundidén i bubbelsortering är följande: man går igenom sekvensen som ska sorteras och letar efter närliggande par som ligger fel (fel inbördes ordning). När man hittar sådana par byter man plats på dem. Man upprepar detta förfarande tills det inte längre behövs några byten och då är hela vektorn sorterad.

Man kan nu göra flera trick för att få algoritmen effektivare. En observation är att slutet av sekvensen garanterat blir färdigsorterad i förtid och att man därför inte behöver gå ända till slutet i de följande svepen. Ett annat trick är att det kan löna sig att omväxlande gå framåt och bakåt genom sekvensen. Implementera gärna en riktigt naiv variant och en som innehåller någon eller några fiffigheter. Märks det någon skillnad i körtiden?

Det finns flera olika sätt att jämföra strängar i Java beroende på ifall man vill att stora och små bokstäver ska hanteras lika och om svenska tecken ska komma i rätt ordning eller ej. Du får gärna använda de mer avancerade jämförelsemetoderna men det är inget krav. Den enklaste jämförelsen får man genom att använda metoden compareTo som är definierad för strängar.

I diagrammen ska du ha med en kurva som visar den teoretiska körtiden baserat på den asymptotiska komplexiteten för algoritmen. Det finns då en godtycklig skalkonstant som du bör sätta till ett lämpligt värde så att kurvan följer dina mätta värden så bra som möjligt. I både matlab och gnuplot (senaste versionen) finns det funktioner för att automatiskt välja parametrar för att få en funktion att passa till mätvärden. Använd i första hand linjära skalor på axlarna i diagrammen men gör gärna även ett log-log diagram för att se hur samma kurvor ser ut där.

När du analyserar den inbyggda sorteringsmetoden (java.util.Arrays.sort) måste du anpassa dig till att denna metod bara kan sortera objekt som ligger lagrade i vektorer. Här kan man alltså inte gå genom samma gränssnitt mot datastrukturen som bubbelsorteringen gjorde. Här får vi helt enkelt acceptera att algoritmen opererar direkt på den verkliga lagringen (som måste vara en vektor). Det är inte heller klart definierat vilken sorteringsalgoritm som används. Det kan faktiskt variera beroende på vilken Java-installation du använder. Du måste alltså gissa vilken asymptotisk komplexitet som gäller. Använd de datavärden du får fram samt kunskap om hur snabba olika sorteringalgoritmer är för att göra en intelligent gissning.

Lycka till!