Lab 2 - Sortering och sökning

Inledning

Den här labben består av två delar. I del 1 ska ett antal sorteringsalgoritmer implementeras, och del 2 behandlar sökning.

Del 1 - sortering

Uppgiften

Den här uppgiften går ut på att få prova på att implementera några olika sorteringsalgoritmer. I den här labben får ni integrera er kod i ett givet kodskelett, där de olika sorteringsalgoritmerna visas grafiskt.

Vektorer med heltal ska sorteras. Varje heltal ska visas som en stapel vars höjd motsvarar talets storlek. Dessa staplar ska sedan byta plats allt eftersom sorteringsalgoritmen utförs. Applikationen ska visa flera olika sorteringsalgoritmer i samma fönster för att det ska gå att visuellt jämföra dem. Till er hjälp finns det ett kodskelett att utgå ifrån, och labben är uppdelad i flera steg där ni gör en liten del i varje steg. Slutresultatet ska se ut ungefär som nedan.

Längst ner i fönstret finns ett antal kontroller som används för att styra sorteringen. I den övre raden finns knappar som organiserar om vektorn:

  • scrambled: talen slumpas utan dubletter
  • randomized: talen slumpas med dubletter
  • nearly sorted: talen läggs nästan sorterat, de flyttas bara om lite
  • decreasing order: talen läggs baklänges med det största först
  • increasing order: talen läggs sorterat

På nästa rad kan man fylla i storleken på vektorn och maxstorlek på talen i vektorn. Dessa värden används nästa gång man organiserar om vektorn med en knapp. Maxstorleken används bara om man väljer att slumpa talen (randomized). Det man skriver in här används dessutom bara om det är en siffra mellan 10 och 200. Radioknapparna är till för att man ska kunna ställa in hur mycket ett byte ska kosta jämfört med en jämförelse. Detta innebär att om man väljer 1 här så tar ett byte lika lång tid som en jämförelse, väljer man 2, dubbelt så lång tid, och väljer man 3 tredubbelt så lång tid.

Dessa inställningar gör att man kan prova de olika sorteringsalgoritmerna under olika förutsättningar. Utnyttja detta för att kunna jämföra algoritmerna under olika förutsättningar, det kan till exempel vara så att en algoritm är bäst om vektorn är nästan sorterad, och en annan är bäst om den är baklänges sorterad.

Underst finns ett reglage som styr animeringens hastighet. Dessutom finns två knappar. De stänger ner hela applikationen respektive startar animationen.

Ovanför knapparna finns en yta där sorteringen för varje algoritm visas och där algoritmens namn även står.

Kodskelett

Kodskelettet finns här. För att öppna den komprimerade filen, gå till den katalog där ni vill arbeta med labben, och skriv: 

 tar -zxvf lab2skelett.tar.gz

API dokumentationen för programmet är tillgänglig här, om ni är nyfikna på koden. Det är dock inte meningen att ni ska kunna förstå den givna koden i detalj. En hel del är överkurs, t.ex. kodningen av grafik och synkroniseringen av de olika algoritmerna.

De flesta av klasserna i kodskelettet ska ni inte göra något med. I varje steg står det angivet vilken klass som ska skapas eller modifieras.

Steg 1 - Komma igång

Testa först att köra programmet, genom att köra: 

  java AnimationStarter
och kontrollera att den startar som den ska. I den givna versionen ska bara bubble sort visas. Testa att köra den på några olika sätt, för att bekanta er med gränssnittet.

Testa sedan att lägga till flera algoritmer. Klassen ImprovedBubbleSortAlgorithm är en förbättrad version av BubbleSort, som avslutas om inga swaps gjorts i en av de yttre iterationerna. Lägg till den i applikationen, så att två algoritmer vissas, vanlig bubble sort, plus den förbättrade. För att åstadkomma detta så ändrar man i main-programmet i AnimationStarter. Lägg där till klassen ImprovedBubbleSortAlgorithm på samma sätt som klassen BubbleSortAlgorithm är tillagd. För att kompilera koden kör ni enklast: 

	javac *.java

Lägg sedan till selection sort, som finns implementerad som klassen SelectionSortAlgorithm, och testkör igen.

Även quick sort finns implementerad i klassen QuickSortAlogrithm. Den är implementerad så att den väljer pivot som medianen av tre värden. Lägg till även den och testkör igen.

I fortsättningen av labben kan ni ta bort någon av bubble sort versionerna, för att få plats med de övriga algoritmerna.

Steg 2 - Insertion sort

I detta steg ska ni själva implementera och lägga till sorteringsalgoritmen insertion sort.

Alla sorteringsalgoritmer som läggs till ska implementeras som en egen klass som ärver från SortAlgorithm. För varje algoritmklass behövs en konstruktor samt metoden sort(). Ibland kan det dessutom behövas någon hjälpmetod till sort. Konstruktorn anropar basklassens (SortAlgorithms) konstruktor. Dit ska även namnet på algoritmen i fråga skickas med.

För att kunna sortera använder man metoderna swap för att byta plats på två tal och cmp för att jämföra två tal. Dessa metoder ligger i SortAlgorithm. Ta reda på hur de fungerar via API:t och koden. Förutom att byta plats på/jämföra tal så ser dessa båda metoder till att grafiken uppdateras och att de olika algoritmerna synkroniseras. Det är viktigt att använda just dessa två metoder och inget annat för sorteringen för att applikationen ska fungera korrekt.

Utöver dessa två metoder finns det ytterligare en metod i SortAlgorithm som ni kommer att behöva. Det är elementCount(), som ger vektorns längd. Titta gärna på hur de givna sökalgoritmerna är implementerade som hjälp i detta steg!

I det här steget ska ni alltså implementera en egen version av insertion sort. Labskelettet ställer lite extra krav på hur den sroteras, eftersom ni inte ahr tillgång till värdena i arrayen, utan enbart till de tre metoderna som beskrivs ovan. Detta innebär att ni inte kan plocka ut ett värde ur arrayen, och jämföra respektive byta med det, vilket ni måste ta hänsyn till vid implementationen. När ni har implementerat insertion sort ska den läggas till i visualiseringsfönstret, så att bubblesort, quick sort, selection sort och insertion sort visas. Detta görs som i steg 1. Testa ordentligt med olika typer av vektorer att er algoritm fungerar som det ska.

Steg 3 - Shellsort

I detta steg ska shellsort implementeras. Tillvägagångssättet är samma som i steg 2.

Shellsort finns ej med i Eck-boken. Den finns dock beskriven i den alternativa boken av Schaffer i kapitel 7.3

Shellsort kan köras med olika gapsekvenser. I sin ursprungsvariant använde Shell en gapsekvens där man dividerar gapet med 2. Det har dock visat sig att shellsort blir mer effektiv med andra gapsekvenser, och det finns många förslag på sådana. I denna uppgift ska ni köra med en variant av Gonnets sekvens, där gapet divideras med 2,2 (och avrundas nedåt). Ni måste här tänka på att det sista gapet måste vara 1, för att sorteringen ska fungera. Det första gapet initialiserar ni till vektorns längd/2, avrundat nedåt.

När algoritmen är implementerad ska den läggas till i fönstret som sedan ska visa minst fem olika algoritmer.

Steg 4 - Testa, jämför och analysera

Labkoden synkroniserar de olika algoritmerna med avseende på byten och jämförelser. I default-varianten "kostar" ett byte och en jämförelse lika mycket, vilket inte är helt realistiskt. Detta kan ändras genom att använda radioknapparna där det står "Weight för swaps" i gränssnittet, där kostnaden för ett byte jämfört med en jämförelse kan ökas på upp till 3. Testa och kör algoritmerna med olika värden här.

Synkroniseringen av algoritmerna tar inte hänsyn till andra beräkningar och operationer som eventuellt utförs i algoritmerna. Till exempel räknas inte tiden in som det tar för improved bubble sort att kontrollera ifall några byten har skett i en iteration. Detta gör att jämförelsen kan bli något orättvis, men i allmänhet är tiden för övriga operationer försumbar i jämförelse med tiden för byten och jämförelser, och ni kan därför bortse från detta.

Provkör de fem olika algoritmerna, både era egna och de givna, och jämför dem under olika förutsättningar, olika stora vektorer initialiserade på olika sätt och olika vikter för byten. Skriv en kort diskussion, cirka en A4-sida, där ni diskuterar resultaten, och jämför dem med den teoretiska tidskomplexiteten för algoritmerna.

Del 2 - sökning

Kod att arbeta med: Searching.java

Föreläsningarnas två sökalgoritmer finns implementerade i klassen Searching för arrayer med heltal. Binärsökning är impleemnterat både i en rekursiv och en iterativ variant. I den givna koden görs sökningen i arrayer med heltal.

Programmet går att köra som det är, och ska visa utskriften: 

---------------------------------------------

Linear search of 89 in : 93,42,78,11,32,89,44,57,13,95,32,12,
Result     5
---------------------------------------------

Binary search (rec) av 89  in : 11,12,13,32,42,44,57,78,89,93,95,
Result     8
---------------------------------------------

Binary search (not rec) of 89 in : 11,12,13,32,42,44,57,78,89,93,95,
Result     8
---------------------------------------------


Linear search of 55 in : 93,42,78,11,32,89,44,57,13,95,32,12,
Result     -1
---------------------------------------------

Binary search (rec) av 55  in : 11,12,13,32,42,44,57,78,89,93,95,
Result     -1
---------------------------------------------

Binary search (not rec) of 55 in : 11,12,13,32,42,44,57,78,89,93,95,
Result     -1
---------------------------------------------

Uppgift

Uppdatera sökklassen så att den dels använder sig av Javaklassen ArrayList istället för en vanlig array, dels så att klassen blir generisk, det vill säga inte är begränsad enbart till heltal utan klarar av godtyckliga objektstyper. När klassen är parametriserad behöver även main-metodens testprogram uppdateras för att återspegla detta genom att använda ArrayList<Integer> för heltal. Tänk även på att du nu måste uppdatera initialiseringen av listorna i main-programmet. Lägg även till nya tester för listor med någon annan typ än heltal, till exempel String, för att visa att din uppdaterade kod är generisk.

Testkör ditt uppdaterade testprogram, och se till att utskriften är korrekt.

Tips

För att underlätta kan det vara bra att göra lösningen i flera steg. En lämplig lösningsgång är följande.

  1. Gör om koden så att ArrayList<Integer> används istället för int[]. Gör detta både för alla metoder i klassen, inklusive main-metoden.
  2. Gör om sökningskoden så att den kan användas för generiska ArrayList. Testkoden ska fungera även då.
  3. Lägg till ny testkod för ArrayList<String> för att ytterligare testa din generiska kod

När ni gör binärsökningen generisk behöver ni kunna hantera generiska jämförelse. Läs mer i Eck 10.1.6!

Examination

Bifoga följande i ett mail till din labassistent:

  • Källkoden till samtliga klasser i del 1 och 2, inklusive de givna. Koden ska följa kodstandarden och vara enhetligt indenterad.
  • En skärmdump av det grafiska programmet i del 1.
  • En utskrift för ditt testprogram i del 2.
  • En kort diskussion (cirka en A4-sida) kring de olika sorteringalgoritmerna för steg 1.4.

Checklista för inlämnat material:

  • Är alla delar inlämnade?
  • Används lämpliga och tydliga namn för klasser, metoder och variabler?
  • Följer koden kodstandarden?
  • Är koden enhetligt indenterad?
  • Är koden kommenterad enligt kodstandarden?
  • Uppfyller programmen kravspecifikationen?
  • Är diskussionen kopplad till teori?

Del 1 är ursprungligen skapad för kursen TDDC30 vid Linköpings universitet av Sara Stymne. Del 2 är delvis baserad på en tidigare lab för 5LN446 av Mats Dahllöf och Evelina Andersson. Båda delarna är uppdaterade av Sara Stymne 2013 för 5LN446.