TDDC30 - Programmering i Java, datastrukturer och algoritmer

Från Studieboken - Skapad av och för studenter
Hoppa till: navigering, sök
TDDC30
TDDC30 page image.png
Institution Institutionen för datavetenskap (IDA)
Examinator Torbjörn Jonsson
Kursledare Erik Nilsson
Examination Laborationer (3 hp)
Datortentamen (3 hp)
Högskolepoäng 6 hp
Undervisas för Industriell ekonomi
Systemvetenskap
Övrigt Kursplan
Tentastatistik
Kurshemsida

TDDC30 är en grundkurs i programspråket Java, datastrukturer och algoritmer. Kursen omfattar 6 högskolepoäng och undervisas både för Industriell ekonomi och för SystemvetenskapLinköpings universitet. Kursen är en påbyggnadskurs på TDDD11 - Programmering, grundkurs och förutsätter att studenten har grundläggande programmeringskunskaper gällande ett "programmeringstänk".

Kursen går igenom ett antal sorteringsalgoritmer, olika typer av datastrukturer, hur man skriver och använder UML-diagram, hur man använder det grafiska Swingpaketet och allmänt hur man ska tänka för att programmera objektorienterat. Examinationsmomenten innefattar 5 stycken laborationer (0-4) och en tentamen. Tentan består av en teoretisk del och en praktisk programmeringsdel.

Java

Java är ett av världens mest använda programmeringsspråk, just för dess operativsystemsneutralitet. I programspråket ADA som kursen TDDD11 undervisas i så använder man en kompilator som tolkar den källkod som programmeraren skrivit och gör om den till maskinkod som datorn kan köra. I Java så finns det ett mellanlager som kallas för Java Virtual Machine (JVM). JVM gör det möjlig att köra samma javakod på alla operativsystem som har stöd för detta, vilket i stort sett gör språket plattformsoberoende, det går lika bra att köra javakod i en Androidtelefon som på en Mac.

Språket är uppbyggt på klasser som på olika sätt kommunicerar och interagerar med varandra.
Wikipediaartikeln

Konstruktorer

Varje gång man skriver en ny klass så skapas en konstruktor, skriver man ingen egen så skapas automatiskt en tom utan inparametrar. Konstruktorn skrivs ungefär som en metod i klassen där metodnamnet är namnet på klassen. Den används sedan när man initierar klassen som ett objekt. Via konstruktorn kan man skicka med data som är bra vid skapandet av objektet. Skriver man t.ex klassen Human så är det rimligt att lägga namn och ålder som inparametrar i konstruktorn, då alla människor har ett namn och en ålder. I konstruktorn kan man också skriva kod som man vill ska köras varje gång som en klass instansieras.

Här är ett exempel på hur konstruktorn skrivs:

public class Cat { // Publika klassen Cat
     
     private String name; // Instansvariabel för kattens namn
     private int age;  // Instansvariabel för kattens ålder
     
     public Cat (String name, int age) { // Detta är huvudet av konstruktorn. Vi tar in kattens namn och ålder
          this.name = name; // Vi tilldelar instansvariabeln "name" med inparametern "name"s data
          this.age = age; // Vi tilldelar instansvariabeln "age" med inparametern "age"s data
          System.Out.println("The cat's name is " + name + " and the age of the cat is " + age); // Utskrift av namn och ålder
     }
}


När man sedan instansierar ett objekt av klassen Cat skriver man på följande sätt:

Cat kattenKalle = new Cat("Kalle", 10); // Vi skickar in namnet "Kalle" och åldern 10 i konstruktorn
Cat kattenPelle = new Cat("Pelle", 2); // Vi skickar in namnet "Pelle" och åldern 2 i konstruktorn


Wikipediaartikeln

Objektorientering

Objektorienterad programmering bygger på program som består av en uppsättning objekt som interagerar med varandra på olika sätt.

Objekt


Wikipediaartikeln

Klass

Java är ett objektorienterat språk som är uppbyggt på b.la klasser. En klass är ett eget kodstycke som är en mall man använder för att skapa ett objekt i Java. I klassen skriver man instruktioner om hur just den klassen/objektet fungerar. Instruktionerna (klassen) består av importering av paket, attribut och metoder. Se följande exempel:

package test; // Denna klass tillhör paketet "test"

// Detta är en kommentar. Kommentarer i Java skrivs med två stycken slash följt av en text
import java.grafisktpaket.* // Stjärnan (*) betyder att vi importerar precis alla klasser i paketet grafisktpaket
import java.util.ArrayList; // Här hämtar vi enbart klassen "ArrayList". Det är viktigt att inte hämta onödiga klasser som inte används


private int nummer; // Här skapar vi en private integer (heltalsvariabel) med namnet nummer
private double nummer2; // Här skapar vi en private double (decimalvariabel) med namn nummer2
private String namn; // Här skapar vi en private String (textsträng) med namnet namn
private boolean check; // Här skapar vi en private boolean (tvåvärdesvariabel) med namn check


public class skrivText() { // Klassen heter skrivText och är public (dvs synlig för alla).
        System.out.println("Hello World!"); // Här skrivs "Hello World!" ut i konsolen.
}

För att skapa ett objekt så instansierar man en klass, detta görs i koden man vill skapa objektet. I nedanstående exempel instansierar vi klassen ArrayList. Detta sker i två steg:

  1. Skapa en referens som ska peka på ett objekt skapat kring en specifik klass.
  2. Instansiera själva objektet och peka referensen på objektet.


ArrayList<String> list; // Steg 1: Här skapar referensen "list" till ett ArrayList-objekt.
list = new ArrayList<String>(); // Steg 2. Här skapas själva ArrayList-objektet som referensen "list" pekar på.

Detta kan även göras genom att skriva ihop de två stegen:

ArrayList<String> list = new ArrayList<String>();


Wikipediaartikeln

Synlighet

Synlighet används för att begränsa insynen och dölja implementationen av klasser, metoder och attribut. Som regel ska man visa upp så lite som möjligt, endast det som verkligen är nödvändigt. Attribut är av god sed och vana private, därför måste man komma åt dem på något annat sett. Detta gör man via getters and setters. Getter är en metod som hämtar attributet, Setter är en metod som sätter ett nytt värde på attributet.

public class testMetod() {

     private int number = 0;

     public int getNumber() { // Getter returnerar integern number
          return number;
     }

     public void setNumber(int number) { // Setter sätter number till inparameterns värde
          this.number = number;
     }
}


Olika synlighet
Synlighet Klass Paket Subklass Värld
public Ja Ja Ja Ja
protected Ja Ja Ja Nej
private Ja Nej Nej Nej


God sed och vana
Klasser Som regel public. Används de endast internt kan mer begränsad synlighet användas
Metoder public
Interna metoder private
Attribut private (eventuellt protected om motivetat)

Statiska metoder och attribut

Om en metod eller ett attribut hör till hela klassen i sig än en specifik instans (objekt) så ska den göras statisk. De kallas då för klassmetoder och klassvariabeler. Ett exempel på detta skulle kunna vara i ett program där man har användning för vilket år det är. Det finns ingen mening att skapa ett nytt attribut med samma år för varje objekt som instansieras. När den görs statisk så lagras attributet enbart på ett minne som tillhör klassen i sig, det vill säga oavsett hur många objekt av klassen som instansieras så skapas bara ett minnesutrymme för attributet. Detta betyder också att man kan kalla på attributet från andra klasser i samma paket utan att instansiera klassen som ett objekt.

public class Program {
     public static int year = 2016; // Statiskt attribut
}

public class OtherProgram { // Klassen otherProgram ligger i samma paket som Program
     int currentYear = Program.year; // Vi tilldelar variabeln currentYear värdet 2016 genom att kalla på klassvariabeln year i klassen Program
     System.Out.println(currentYear); // Detta kommer att skriva ut 2016 på skärmen
}

Arv och polymorfism

Arv är en stor del av objektorienterad programmering. Varje klass består av instruktioner i form av metoder och attribut. Säg att vi har en klass som heter Dog. Varje hund måste kunna äta, gå och sova, så metoderna eat(), walk() och sleep() känns nödvändiga. Men vi nöjer oss inte med att vara så generella som att enbart ha en klass för alla hundar, utan vi vill skapa en specifik klass för just Golden Retrievers, så vi skapar klassen GoldenRetriever som ärver från klassen Dog. Nu är vår klass Dog en superklass och vår klass GoldenRetriever en subklass till Dog. En Golden Retriever gillar en viss typ av mat som andra hundar inte gillar, därför måste vi skriva en ny unik metod av eat() i vår nya subklass. Det vi nu gör kallas för att överskugga (override) en metod. När vi nu kallar på metoden eat() för ett GoldenRetriever-objekt så kommer den klasspecifika metoden att köras och inte den generella i klassen Dog. Däremot om vi kallar på metoden sleep() för ett GoldenRetriever-objekt så kommer den generella metoden för klassen Dog köras, då alla hundar sover på samma sätt och ingen ny klasspecifik metod har skrivits. Det är alltså möjligt att kalla på samtliga metoder i superklassen. Väljer man däremot att skriva över metoden med en subklass-specifik metod så körs den istället.

Klassen Dog

public class Dog { 

     public void eat() {
          .....
     }

     public void walk() {
          .....
     }

     public void sleep() {
          .....
     }
}


Klassen GoldenRetriever

public class GoldenRetriever extends Dog { // För att ärva från en annan klass skriver man "... extends KLASSNAMN" 

     private int age = 7;

     public void eat() { // Metoden overridear metoder eat() i klassen Dog
          .....
     }

     public int getAge() {
          return age;
     }
}

Om man vill tvinga fram att en subklass måste implementera vissa specifika metoder från dess superklass så gör man de metoderna abstrakta i superklassen. Har man en abstrakt metod i sin superklass så blir hela superklassen abstract. En abstrakt klass kan inte instansieras. I fallet ovan skulle metoden eat() kunna vara ett exempel på en metod som kan vara bra att göra abstrakt, då alla hundar äter olika typ av mat.

Abstrakta klassen Dog

public abstract class Dog { // Klassen Dog är abstrakt och kan inte instansieras

     public abstract void eat(String food); // Metoden är abstrakt och måste implementeras av varje klass som ärver av klassen Dog

     public void walk() {
          .....
     }

     public void sleep() {
          .....
     }
}


Polymorfism kommer från grekiskan poly-morf som betyder många former. Säg att vi skriver en metod och vet att vi kommer att få in en hund som inparameter, men inte exakt vilken hund (subklass), det kanske är en Golden Retriever, eller en Tax. I detta fallet så använder vi polymorfism. Då skriver du enbart klassen Dog som inparameter och lämnar det öppet exakt vilken hund-typ som kommer att skickas in. Det är inte förens i körögonblicket som det bestäms.

public class Kennel {
     public static void addDog (Dog dog) {
          .....
     }

     public static void main(String[] args) { 
          GoldenRetriever kalle = new GoldenRetriever(); // Vi skapar en ny GoldenRetriever
          Kennel.addDog(kalle); // Vi skickar in en GoldenRetriever in i addDog, vilket är okej då det är en subklass till Dog och är tillåtet enligt polymorfi
     }
}

Wikipediaartikeln

Loopar

En loop är ett kodstycke som i sin tur upprepar ett annat kodstycke ett visst antal gånger. Det finns egentligen två loopar som användes mycket i kursen: While-loop och For-loop.

While-loop
En While-loop används då man från början inte vet exakt hur många gånger loopen ska köras, men man kan med ett villkor bestämma det. Så länge villkoret är uppfyllt så körs loopen. Viktigt är att det finns en variabel i villkoret som förändras under varje loop, annars kommer loopen att gå i all evighet. Ett exempel kan vara att man letar efter ett visst värde i en lista, vi slutar loopen när vi hittat värdet. Det programmet kan se ut på följande sätt:

ArrayList<Integer> listOfNumbers = new ArrayList<Integer>(); // Vi skapar en ArrayList av Integers (siffror)

add.listOfNumbers(1); // Vi lägger till ett antal siffror i vår lista
add.listOfNumbers(2);
add.listOfNumbers(3);
add.listOfNumbers(4);
add.listOfNumbers(5);

private int counter = 0;

while (listOfNumbers(counter) != 3) {
     ++counter;
}

System.Out.println(counter); // Siffran 3 kommer att skrivas ut i terminalen


(konceptet while-loop är samma för både programspråket C och Java)
Wikipediaartikeln


For-loop
For-loopen är en typ av While-loop, även den har ett villkor i sig och så länge som villkoret är uppfyllt så körs loopen. For-loopens huvud är uppdelat i tre delar:

  1. Deklaration av integer som används som en counter
  2. Villkor
  3. Hur countern ska förändras


Om vi skriver samma exempel som ovan, fast med en for-loop, skulle det kunna se ut såhär:

ArrayList<Integer> listOfNumbers = new ArrayList<Integer>(); // Vi skapar en ArrayList av Integers (siffror)

add.listOfNumbers(1); // Vi lägger till ett antal siffror i vår lista
add.listOfNumbers(2);
add.listOfNumbers(3);
add.listOfNumbers(4);
add.listOfNumbers(5);

private int forPrint;

// Vi skapar integens i som börjar med värdet 0. Detta är vår counter
// Så länge villkoret listOfNumbers(i) != 3 så körs loopen
// Varje varv loopen körs så ökar countern med 1
for (int i = 0; listOfNumbers(i) != 3; ++i) { 
   forPrint = i;
}

System.Out.println(forPrint); // Siffran 3 kommer att skrivas ut i terminalen



(konceptet while-loop är samma för både programspråket C och Java)
Wikipediaartikeln

Unified Modelling Language (UML)

UML-diagram
Ett UML-schema beskriver relationen mellan klasser

Unified Modeling Language (UML) är ett objektorienterat sätt att modelera system som beskriver hur olika klasser hör ihop. Ett klassdiagram (som du ser till höger) är en beskrivning över en klass, vad klassen heter, vilka attribut/variabler klassen har och dess metoder. Det beskriver också vilken access varje attribut och metod har genom ett "prefix" (tecken) som skrivs innan attributet/metoden. Det beskriver dessutom vilket indata varje metod har, samt om metoden returnerar något data.

Access klassdiagram
Prefix Access Explanation
+ public Synlig för klassen, paketet, subklasser och värld.
- private Synlig enbart i klassen
# protected Synlig för klassen, paketet och subklasser.
understruken static Ett static attribut behöver inte instanseras för att användas.
italic abstract Klassen kan inte instanseras och innehåller metoder som måste implementeras.

Ett fullt UML-schema beskriver vilka relationer klasserna har till varandra och om en klass ärver eller implementerar en annan klass. Schemat beskriver även om en klass använder, äger eller "har" en annan klass.

UML-arv. Animal är superklass som subklasserna Cat och Dog ärver ifrån







Wikipediaartikeln

Datastrukturer

Träd

En trädstruktur bygger på en rotnod som är "grunden" i trädet. Det är i roten som all avsökning börjar och det är även i roten som man tar bort objekt ur trädet. Varje nod innehåller det datat man vill lagra, det kan till exempel vara siffror, filmtitlar, personnummer osv. Noden har sedan en referens i sig som pekar på dess barn.
Ett träd har följande uppdelning:

Träd
Tre olika typer av träd
  • Rot: Grundnoden
  • Förälder: Förälder till noden under sig
  • Barn: Barn till noden över sig
  • Syskon: Två noder som har samma förälder
  • Gren: Ett träd kan ha flera grenar. Varje gren har en toppnod och en egen trädstruktur
  • Löv: Nod som inte har några barn


Träd delas också in i tre olika kategorier beroende på dess nodstruktur:

  • Perfekt träd: Alla nivåer är fyllda. Det vill säga alla noder har två barn, förutom löven
  • Fullt binärt träd: När alla noder antingen har noll eller två barn
  • Fullständigt binärt träd: Är ett perfekt träd som saknar några av de högraste löven



Wikipediaartikeln

Heap

En heap bygger på en fullstädig trädstruktur där varje nod högst kan ha 2 stycken barn. Det finns två typer av heapar: Maxheap och Minheap.

Maxheap
Minheap

Maxheap

  • Roten har det största värdet i heapen
  • Varje barn har ett mindre värde än sin förälder
  • Vid borttagning tas rotnoden bort. Den ersätts med den sista noden i heapen (noden som är längst till höger i nedersta leveln). Där efter tittar man om nått av barnen är större än den nya roten. Finner man ett barn som är större, byt dem. Där efter fortsätter man titta på barnen och ser om nån av de två nya barnen är större än noden. Är båda barnen större, byt med den största.
  • Vid inaddering av en nod, lägg den sist i heapen (dvs på nästa tomma plats, längst ner i heapen, sett från vänster). Där efter, se om noden är större än sin förälder. Om ja, byt plats, om nej stanna. Fortsätt tills noden har hittat sin rätta plats.

Maxheap visualisering

Minheap

  • Roten har det minsta värdet i heapen
  • Varje barn har ett större värde än sin förälder
  • Vid borttagning tas rotnoden bort. Den ersätts med den sista noden i heapen (noden som är längst till höger i nedersta leveln). Där efter tittar man om nått av barnen är mindre än den nya roten. Finner man ett barn som är mindre, byt dem. Där efter fortsätter man titta på barnen och ser om nån av de två nya barnen är mindre än noden. Är båda barnen mindre, byt med den minsta.
  • Vid inaddering av en nod, lägg den sist i heapen (dvs på nästa tomma plats, längst ner i heapen, sett från vänster). Där efter, se om noden är mindre än sin förälder. Om ja, byt plats, om nej stanna. Fortsätt tills noden har hittat sin rätta plats.

Minheap visualisering

Wikipediaartikeln

Binärt sökträd

Binärt sökträd

Ett binärt sökträd består även det av en trädstruktur, dock inte nödvändigtvis ett fullständig träd. Ett binärt sökträd har följande egenskaper:

  • Varje nod har ett värde
  • Nodens vänstra barn och alla andra noder i det vänstra benet ska ha ett mindre värde än noden själv
  • Nodens högra barn och alla andra noder i det högra benet ska ha ett större värde än noden själv

Wikipediaartikeln

Kö (Queue)

Queue

En kö är precis vad det låter, först in först ut (FIFO, First In First Out). Tänk dig att du är en kassörska. Det kommer in massa kunder som ställer sig i kö och du hjälper dem en efter en precis i den ordningen som de kom in. Det vill säga, det som har väntat längst får också hjälp först. Kommer det en ny kund så placeras denna sist i kön och får vänta tills alla framför har fått hjälp.

Metoder som används i en kö:

  • front()/peak(): Returnerar det värdet som är längst fram i kön
  • void enqueue(E): Datat E längst till i slutet av kön
  • dequeue(): Returnerar och tar bort det värdet som är längst fram i kön
  • int size(): Returnerar storleken på kön, dvs antal element.
  • boolean isEmpty(): Returnerar sant om kön är tom, returnerar falskt om kön ej är tom


Visualisering av queue (länkad lista)
Visualisering av queue (array)

Stack

Stack

En stack fungerar som en stapel tallrikar, där varje tallrik representerar ett värde i stacken. Varje gång man lägger till ett ny tallrik (värde) i stacken så hamnar den nya tallriken högst upp. Varje gång man tar en tallrik från stacken så tar man den man senast la, det vill säga sist in, först ut (LIFO, Last In First Out).

Metoder som man använder i en stack:

  • top()/peek(): Returnerar det elementet som är på toppen av stacken utan att ta bort det
  • void push(E): Lägger elementet E på toppen av stacken
  • pop(): Returnerar och tar bort elementet som ligger på toppen av stacken
  • int size(): Returnerar storleken på stacken, det vill säga antalet element
  • boolean isEmpty(): Returnerar sant om stacken är tom, returnerar falskt om den inte är tom


Visualisering av stack (länkad lista)
Visualisering av stack (array)

Listor

Enkellänkad lista
Dubbellänkad lista
Cirkulärt dubbellänkad lista

Det finns olika typer av listor, det som dock är gemensamt för alla listor är att:

  1. Varje nod innehåller ett data
  2. Varje nod innehåller en eller flera referenser till samma typ av nod

Det som skiljer mellan de olika listorna är hur noderna är sammankopplade.

Enkellänkad lista
I en enkellänkad lista har varje nod en referens som refererar på nästkommande nod i listan. Detta gör att det enbart går att komma åt noder/värden som ligger efter den noden man "är på".

Dubbellänkad lista
I en dubbellänkad lista har varje nod två referenser, den ena refererar till noden före och den andra refererar till noden efter. Detta gör det möjligt att komma åt noder både före och efter noden man "är på".

Cirkulärt dubbellänkad lista
En cirkulärt dubbellänkad lista är en dubbellänkad lista där slutnoden (sista noden i listan) är ihopkopplad med den första noden och vice versa.

Iterator

Traversering

Traversering innebär att man läser av (och skriver ut) alla noderna i ett träd i en speciell ordning. Det finns 4 olika sätt att traversera: Level-traversering, preorder-traversering, inorder-traversering och postorder-traversering. Ett enkelt sett att tänka vid pre-, in- och postorder är att varje nod är en cirkel med tre stycken kontaktpunkter: Vänster, botten och höger. Beroende på vilken typ av traversering man är ute efter väljer man att fokusera på en av de tre kontaktpunkterna. Varje traversering börjar sedan på rotnodens vänstra sida. Följ därefter vänster ytterkant runt hela trädet tills du är tillbaka vid startläget. Varje gång du stöter på den kontaktpunkten som korresponderar med den traverseringen du gör så skriver du ut värdet i noden.

Levelorder-Traversering
Vid Levelorder-traversering läser man av noderna och dess värde, från vänster till höger och nivå för nivå.
E, C, H, A, D, F, B, G

Preorder-Traversering
Vid preorder-traversering fokuserar du på vänster kontaktpunkt, det vill säga varje gång du stöter på vänster kontaktpunkt så skriver du ut värdet i noden.
E, C, A, B, D, H, F, G

Inorder-Traversering
Vid inorder-traversering fokuserar du på kontaktpunkten som är under noden. Någonting annat att lägga märke till är att värderna är sorterade från minst till högst.
A, B, C, D, E, F, G, H

Postorder-Traversering
Vid postorder-traversering fokuserar du på höger kontaktpunkt.
B, A, D, C, G, F, H, E

Level-traversering
E C H A D F B G
Preorder-traversering
E C A B D H F G
Inorder-traversering
A B C D E F G H
Postorder-traversering
B A D C G F H E

Sorteringsalgoritmer

En sorteringsalgoritm används för att sortera data. Olika algoritmer är olika effektiva beroende på förhållandena där den ska implementeras.

Tidskomplexitet

Varje for-loop är beroende av inparametern "n" och har tidskomplexiteten O(n). I och med att det är en loop i en loop, där båda looparna är beroende av "n", så blir den totala tidskomplexiteten O(n)*O(n) = O(n2).

Att bestämma hur snabb en algoritm är genom att ta tid på hur länge den håller på är svårt, både för att mindre algoritmer går otroligt fort och för att olika datorer kan köra en samma algoritm på olika tid beroende på prestanda hos datorn. Vi behöver alltså ett generiskt sätt att mäta hastigheten, oavsett vilken dator den körs på. Det är här tidskomplexitet och Ordo kommer in i bilden. När vi beräknar Ordo (stora O) för en algoritm börjar vi med att bryta ner den i mindre delar och räknar ut de mindre delarnas tidskomplexitet.

Samtliga primitiva operationer har tidskomplexitet O(1):

    Jämförelser (2>x)
    Aritmetiska operationer (4+x)
    Tilldelning (z = i)
    Arrayindexering (arrayOfNumbers[3])
    Metodretur (return true)
    Objektreferering (humanObject.age)


Om antalet primitiva operationer beror på indatats storlek (t.ex i en for-loop där den primitiva operationen i loopen kör n antal gånger) blir tidskomplexiteten O(n), där n = indata. Skulle det vara ytterligare en for-loop i for-loopen, som även den är beroende av indatat = n så får du tidskomplexiteten O(n)*O(n) = O(n2).
Vid addering och multiplicering av delkomplexiteten så tar man inte hänsyn till konstanter (O(15n4) -> O(n4))

Addition: Vid addition av Ordo så tar man bara hänsyn till den term som är av högst ordning. Exempel:
O(4n) + O(2n3) + O(7n2) = O(n3)

Multiplikation: Vid multiplikation av Ordo så adderar du ihop exponenterna i termerna. Exempel:
O(15n3)*O(22n9) = O(n12)

Kombination: Vid en kombination så tittar du som vanligt först på multiplikationerna, sedan på additionerna. Exempel:
O(n)*O(3) + O(n2) + O(n2)*O(n) = O(n3)

Minst till störst
Tidskomplexitet Benämning
O(1) Konstant
O(log(n)) Logaritmisk
O(n) Linjär
O(nlog(n))
O(n2) Kvadratisk
O(n3) Kubisk
O(2n) Exponentiell
O(n!) Faktoriell
O(nx) Polynomisk

Bubble sort

Bubblesort

Bubble sort-algoritmen är en relativt långsam algoritm med en medeltidskomplexitet på O(n2).

Algoritm
Vi sorterar minst till vänster, störst till höger.

  1. Börja i någon av ändarna (detta fallet vänster)
  2. Jämför de två bredvidliggande värdena. Är vänster större än höger -> Byt plats
  3. Hoppa ett steg till höger. Upprepa steg 2
  4. När algoritmen träffar högerkanten, upprepa steg 1. Upprepa detta tills datat är sorterat

Den kallas Bubble Sort för att den "bubblar" upp värdena längst listan tills de hamnar på sin rätta plats.

Stabil? Ja
Tidskomplexitet

  • Bästa fall: O(n)
  • Medelfall: O(n²)
  • Värsta fall: O(n²)


Shaker sort (Cocktail shaker sort)

Shakersort

Shaker sort är väldigt lik Bubble sort, med skillnaden att man vänder efter varje "varv" och går Höger -> Vänster -> Höger -> Vänster osv, lite som en bartender skakar en shaker.

Algoritm
Vi sorterar minst till vänster, störst till höger.

  1. Börja i någon av ändarna (detta fallet höger)
  2. Jämför de två bredvidliggande värdena. Är vänster större än höger -> Byt plats
  3. Hoppa ett steg till vänster. Upprepa steg 2
  4. När algoritmen träffar vänsterkanten, hoppa ett steg till höger igen och upprepa steg 2
  5. Gör detta fram och tillbaka tills datat är sorterat


Stabil? Ja
Tidskomplexitet

  • Bästa fall: O(n)
  • Medelfall: O(n²)
  • Värsta fall: O(n²)


.

Insertionsort

Insertionsort

Vi delar upp datat i en sorterad och en osorterad del. Från början är hela listan osorterad.

Algoritm

  1. Titta på det första värdet i den osorterade listan och placera den på rätt ställe i den sorterade listan
  2. Upprepa steg 1 tills all data är sorterat


Stabil? Ja
Tidskomplexitet

  • Bästa fall: O(n)
  • Medelfall: O(n²)
  • Värsta fall: O(n²)


Selectionsort

I Selectionsort så delar vi upp datat i en sorterad och en osorterad del. Från början är hela listan osorterad.

Algoritm

  1. Leta upp det minsta värdet i den osorterade listan
  2. Lägg värdet i slutet av den sorterade listan
  3. Upprepa steg 1 och steg 2 tills hela listan är sorterad


Exempel:
425916
425916 // 1 är minst
125946 // Byt 1 och 4
125946 // 2 är minst
125946 // Byt 2 med sig själv
125946 // 4 är minst
124956 // Byt 4 och 5
124956 // 5 är minst
124596 // Byt 5 och 9
124596 // 6 är minst
124569 // Byt 6 och 9
124569

Stabil? Nej
Tidskomplexitet

  • Bästa fall: O(n²)
  • Medelfall: O(n²)
  • Värsta fall: O(n²)


Föreläsningar

Föreläsning 1
Kursinformation
Java
Loopar
Objektorientering

Föreläsning 2
Konstruktorer
Statiska metoder och attribut
Synlighet
Arv och polymorfism
Unified Modelling Language (UML)

Föreläsning 3
Abstrakta datatyper
Listor
Stack
Kö (Queue)

Föreläsning 4
Interface
Generiska klasser
Undantag

Föreläsning 5
Algoritmanalys (Ordo)
Insertionsort
Grafiska komponenter

Föreläsning 6
Bubblesort
Shakersort
Mergesort
[1]
[2]
[3]

Föreläsning 7
Selectionsort
Shellsort
Quicksort
Grafiska användargränssnitt
Swing
[4]

Föreläsning 8
Träd
Traversering

Annat material

Sammanfattningar

Tentor

Tentor (LIU)

Tentaanalys

Tentaanalys

Länkar

Kursplan
Tentastatistik
Kurshemsida

Se även

Industriell ekonomi - Linköpings universitet
TAOP37 - Optimeringslära, fortsättningskurs
TPPE98 - Ekonomisk analys: Ekonomisk teori