TDDC30 Programmering i Java, datastrukturer och algoritmer

Laboration 3 - visualisering av sortering

Uppgiften

Den här uppgiften går ut på att få prova på att implementera några olika sorteringsalgoritmer samt att visualisera dessa. Därmed innebär det också en viss övning i att programmera grafiska gränssnitt.

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.

Er uppgift i labben är att skapa ytan där varje algoritm visas samt att implementera tre stycken sorteringsalgoritmer. Dessutom måste ni lägga in ett antal anrop till det ni gör i den givna koden.

Kodskelett

Kodskelettet finns här. Ni kan ladda ner det antingen komprimerat eller varje fil för sig. Hur man öppnar komprimerade filer beskrivs på labsidan.

Det går att öppna ett projekt med given kod i Eclipse. Starta ett nytt javaprojekt, och välj i första fönstret: "Create project from existing source" och ange i vilken katalog ni lagt filerna från kodskelettet. För att detta ska fungera korrekt så lägg kodfilerna utanför den workspace ni ställt in i Eclipse.

API dokumentationen för programmet är tillgänglig här. Läs igenom hela labinstruktionen och titta igenom kodskelettet och dess API så att ni förstår i stora drag vad labben går ut på och hur applikationen är uppbyggd innan ni sätter igång! Det är dock inte meningen att ni ska kunna förstå precis all den givna koden. En hel del är överkurs, t.ex. synkroniseringen av de olika algoritmerna.

Flera av klasserna i kodskelettet ska ni inte göra något med. I varje steg står det angivet vilka klasser som ska skapas eller modifieras. Dessutom är det angivet i kommentarer i koden och i API:t om en klass behöver ändras och i så fall var.

Steg 1 - Visualiseringsytan

Om man kör programmet som det är givet visas endast inställningsytan. Det som saknas för att programmet ska kunna visa algoritmerna också är visualiseringsytan, klassen AnimationWidget. Att skapa denna är uppgiften i steg 1. När den är skapad ska programmet visa bubblesort när det körs.

Klassen som visar en algoritm heter AnimationWidget. Den ska visa en algoritm med hjälp av staplar som representerar varje tal. Stapelns höjd motsvarar talets storlek. Staplarna ska ha sin bas i botten av widgeten, som i bilden ovan. De ska alltså inte vara "hängande". När flera algoritmer körs senare kommer flera instanser av AnimationWidget att existera samtidigt, en för varje algoritm.

Klassen AnimationWidget ska ärva från en lämplig klass i swingbiblioteket, t.ex. JComponent. Kravet är att man ska kunna lägga in den i en JFrame med metoden add. Den ska visa staplarna som motsvarar talen i vektorn, och namnet på algoritmen den visar. Den ska uppfylla följande krav:

Den ska kunna rita upp hela visualiseringsytan, med alla staplar för talen i vektorn samt namnet på algoritmen.
Den ska rita om bilden när två staplar har bytt plats i vektorn (kan göras antingen genom att rita om hela komponenten eller bara rita om de två staplar som bytt plats).
Den ska visa att algoritmen är avslutad genom att byta färg på staplarna.
Det ska gå att byta ut vektorn som innehåller värdena som sorteras (en metod för detta anropas när man trycker på någon av knapparna för att organisera om vektorn).
Avståndet mellan staplarna och staplarnas höjd ska bero på hur stor ritytan är (getSize()-metoden är bra att kika på här).
VG-del: Visa vilka två tal som jämförs för tillfället genom att markera dessa staplar med en särskild färg. En ny metod måste läggas till i AnimationWidget som anger vilka staplar som ska markeras, sen måste den metoden anropas från någon lämplig plats i den givna koden..
VG-del: Visa vilka två tal som swappats när det sker genom att markera dessa staplar med en särskild färg. En ny metod måste läggas till i AnimationWidget som anger vilka staplar som ska markeras, sen måste den metoden anropas från någon lämplig plats i den givna koden..
VG-del: Om man ändrar storlek på fönstret för mycket, t.ex. gör fönstret väldigt litet, så kan det bli problem med staplarna. Gör så att både staplarnas bredd och mellanrummet mellan staplar beror på fönstrets bredd, så att alla staplar fortfarande har en chans att synas oavsett hur smal ritytan blir (man kanske vill arbeta mest med flyttal istället för heltal här). Här finns ett exempel på hur det kan se ut. Notera hur staplarna aldrig blir så pass små att de inte ritas ut, och att alla 200 staplar trycks in på den begränsade ritytan.

Det som finns i klassen från början är två instansvariabler, en referens till vektorn som sorteras och namnet på algoritmen, och en konstruktor som just nu enbart initierar dessa variabler, men som behöver utökas av er.

Vektorn som ska sorteras ska kunna ha variabel storlek, och talen i den ska kunna ha olika maxstorlek. Både storleken och de enskilda siffrornas maximala värde ska kunna varieras mellan 10 och 200. Detta innebär att utritningen måste anpassas efter detta, och storleken på stolparna beräknas efter vektorns längd resp. maxstorlek på talen, samt fönstrets storlek. Det ska även vara ett mellanrum mellan varje stapel, vars storlek också bör bero på vektorns storlek. Det finns metoder i klassens sortVector för att ta reda på storleken och det maximala värdet.

När ni har implementerat klassen AnimationWidget måste även klassen AlgorithmHandler uppdateras så att den anropar de metoder ni just implementerat. Det finns kommentarer i koden som anger var detta ska göras. Innan dessa anrop har lagts in ska staplarna för default-vektorn (scrambled, storlek 50) visas, men inget kommer att hända när man trycker på kanpparna. Efter att anropen i AlgorithmHandler lagts in ska applikationen gå att köra och visa en instans av bubblesort. Det ska även gå att få nya vektorer i olika storlekar och konfigurationer genom att använda de övre knapparna och reglagen. Prova att köra applikationen för olika storlekar och konfigurationer av vektorn och kolla att det ser snyggt ut!

Om man vill prova på mer grafisk programmering är det tillåtet att ändra i klassen ButtonPanel, vilken är inställningsytan i fönstret. Gör man det kan man ändra utseendet, eller vilken sorts komponenter som används för de olika inställningarna. Alla inställningar ska dock fortfarande gå att göra. Att göra detta är frivilligt.

Tips

Det är lämpligt att bestämma en standardstorlek för ritytan. Detta kan göras med metoden setPreferredSize, som finns för alla klasser som ärver från Component. Prova er fram till en lämplig storlek!
För att rita upp hela komponenten används metoden paintComponent(Graphics), som också finns i alla klasser som ärver från Component, och kan överlagras. Denna metod anropas aldrig explicit sedan utan automatiskt när fönstret behöver ritas om (t.ex. om det varit gömt) eller vid anrop av metoden repaint().
För att kunna rita ut staplarna och namnet är det lämpligt att använda komponenetens Graphics kontext. I Graphics finns bland annat de användbara metoderna setColoroch fillRect. Det finns även en del annat användbart, använd Javas API-dokumentation för att ta reda på mer om detta!

Steg 2 - Visa flera algoritmer samtidigt

Här ska ni få prova att lägga in flera algoritmer samtidigt i fönstret.

klassen ImprovedBubbleSort är en förbättrad version av BubbleSort. 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 AnimatorStarter. I mainprogrammet går det även att ändra hur algoritmwidgeterna placeras, prova gärna det!

Prova återigen att köra applikationen för olika storlekar och konfigurationer av vektorn och kolla att det ser snyggt ut!

I fortsättningen av labben kan ni välja att antingen visa båda dessa två bubble sort varianter eller bara den ena.

Steg 3 - Insertion sort

I detta steg ska ni 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.

Bubblesort är redan implementerad i två versioner, så det kan vara bra att titta på hur de är implementerade som hjälp i detta steg!

När algoritmen är implementerad ska den läggas till i visualiseringsfönstret, så att både bubblesort (en eller två versioner) och insertion sort visas. Detta görs som i steg 2.

Steg 4 - Quicksort

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

Det finns flera varianter av quicksort. Här måste ni implementera en "in-place"-variant, det vill säga en som använder samma vektor hela tiden, och delar upp den i mindre delar via ett start- och slut-index inom vektorn som anger vart i vektorn den är.

Quicksort bygger på att man delar upp listan i två olika delar utifrån ett pivotelement. Pivotelementet kan väljas på olika sätt, vilket påverkar algoritmens effektivitet. I denna lab kan ni välja någon av följande varianter för att välja pivotelement:

Pivotelementet väljs slumpmässigt.
Pivotelementet fås genom att ta medianen av det första, det mellersta och det sista elementet

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

Steg 5 - Shellsort

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

Shellsort finns ej med i boken, men kommer att gås igenom på föreläsning eller lektion. Fråga din assistent om du är osäker på hur shellsort fungerar.

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 någon av följande sekvenser:

Hibbards: {1, 3, 7..., 2^k-1}
Knuths: {1, 4, 13,..., (3^k-1)/2}
Gonnets: Dividera gapet med 2.2 stegvis, avrunda nedåt, se till att det sista gapet blir 1.

Tänk igenom vilket gap som är lämpligt att börja med. Detta val beror givetvis på vektorns storlek.

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

Examination

Bifoga följande i ett mail till din labassistent:

Hela Eclipse-projektet samt källkoden enligt de generella instruktionerna. Alla klasser och publika metoder ska vara kommenterade med javadoc-kommenterar. Koden ska följa kodstandarden och vara enhetligt indenterad.
En kort diskussion (cirka en halv A4-sida) där ni diskuterar hur bra de olika algoritmerna är vid olika förutsättningar. Jämför även era körningar med vad man kan förvänta sig utifrån tidskomlexiteten för de olika algoritmerna.
En separat sida där ni anger ungefär hur mycket tid ni har använt för uppgiften, och några kortfattade reflektioner kring uppgiften. Det kan t.ex vara synpunkter på uppgiften och feedback till lärarna, vad som känns oklart, begrepp som är svåra, osv. (bedöms ej)
Ange tydligt i mailet('VG' i ämnesraden) om ni satsar på VG.

Checklista för inlämnat material:

Är alla delar inlämnade?
Följer koden kodstandarden? Avvikelser ger rest.
Är koden enhetligt indenterad? Slarvig indentering ger omedelbart rest.
Är koden kommenterad enligt kodstandarden?
Används inkapsling? Om det finns fall där instansvariabler accessas utanför klassen ger det omedelbart rest.
Uppfyller programmet kravspecifikationen?
Är alla VG-delar gjorda? (Om ni valde att ge er på det)

Skapad av Sara Stymne 2005, modifierad 2006, modifierad av Jonas Lindgren

Sidansvarig: Jonas Lindgren
Senast uppdaterad: 2013-02-14

Institutionen för datavetenskap