• sekvens: Utför instruktioner i tur och ordning. I Java skrivs sekvenser som satser åtskiljda med semikolon.
• selektion: Välj sekvens av instruktioner beroende på någon viss omständighet. I Java används if- och switch-satserna för selektioner.
• iteration: Upprepa en sekvens av instruktioner flera gånger. I Java finns while-, for- och do-satserna för att uttrycka iterationer ("loopar").
• abstraktion: En namngiven samling instruktioner. I Java används metoder och klasser för att göra abstraktioner.

Tanken med denna lektion är att presentera några standardalgoritmer och diskutera olika möjliga implementationer av dem. I verkligheten behöver man sällan själv skriva dessa algoritmer men de är ändå mycket väl värda att studera som modellexempel på design och analys av algoritmer samt, i vårt sammanhang, kodningsteknik.

Metoderna i denna lektion är placerade i en klass med namnet Algorithms. De är alla skrivna som klassmetoder dvs deklarerade med static och de få all sin information via parametrar (om inte annat explicit sägs).

• Testa primtal
• Euklides algoritm
• Hitta största (eller minsta)
• Linjär sökning
• Instickssortering
• Binärsökning

Ett primtal är ett heltal som bara är jämnt delbart med 1 och sig själv. En uppenbar algoritm för att undersöka om ett tal n är ett primtal är då att gå igenom alla tal j mellan 2 och n-1 och se om n är jämnt delbart med något av dessa.

Det är dock inte nödvändigt att kontrollera alla dessa tal. Eftersom n inte kan vara jämnt delbart med något tal större än n/2 kan man halvera antalet tal att jämföra med.

Det går att begränsa antalet tal ännu mer. Om n inte är ett primtal så kan det skrivas som en produkt p*q av två heltal där det ena måste vara mindre än eller lika med kvadratroten ur n. Detta är en betydande förbättring - för att till exempel undersöka om ett tal av storleken 1 000 000 räcker det med 1000 försök i stället för 500 000.

Hur kan man se om två tal n och j är jämnt delbara?

I Java är det enklast att använda operatorn % som returnerar resten vid en division. (Ett annat alternativ är att utnyttja heltalsaritmetiken: Uttrycket n/j*j == n är true om n är jämnt delbarat med j.)

Vi får då följande metod:

Som synes returnerar metoden false så fort en division som går jämnt ut hittas. Om hela loopen gås igenom så betyder det att ingen division som går jämt ut hittats och true returneras.

Metoden ovan har ett "stilbrott": Man bör alltid kunna se på ett loopvillkoret hur loopen ska sluta. Vi skulle kunna åstadkomma detta t ex med koden

men denna kod är knappast enklare eller lättare att förstå.

(Satsen assert anger villkor för att algortmen ska fungera. Om dessa inte är uppfyllda avbryts programmet. Läs mer om assert i lektion 8!)

Den typiska sättet att hitta det största värdet är att börja med att ansätta ("gissa") ett största värde och sedan gå igenom alla värden och uppdatera gissningen för varje större värde man hittar.

Vad ska man börja med att gissa på? Man måste börja med ett tal som säkert är mindre än eller lika med det maximala värdet. Om man vet att alla tal är positiva skulle man kunna börja med 0. Om man inte vet något om talen kan skulle man kunna börja med Integer.MIN_VALUE som är det minsta möjliga heltalet. Både enklast och bäst är det dock att börja med att gissa att det första talet är störst.

Vi ger här två varianer av lösning: en med en "vanlig" for-sats och en med "for-each"-satsen:

Om man bara ska söka i en del av arrayen (t ex de n först elementen) eller vill veta index för det största elementet så passar inte for-each-loopen.

Övning: Skriv en metod som returnerar index för det största elementet i en array

Att leta efter största (eller minsta) värdet i en array kan lösas genom att sortera arrayen och sedan se vilket som kom på första eller sista plats. Sortering är dock en betydligt mer tidsmässigt krävande och kodmässigt mer komplicerad operation varför den givna algoritmen är att föredra.

Det enklaste sättet att se om ett visst värde finns i en array är att använda så kallad linjär sökning. Det betyder att man tittar på elementen i tur och ordning. Om man upptäcker elementet avbryter man och noterar att det sökta elementet finns. Om man gått igenom hela arrayen utan att hitta det noterar man att det inte finns.

Antag att vi har en ArrayList<Integer> a med heltal lagrade i storleksordning med det minsta först och att vi vill lägga in ett talx i listan så att den fortfarande är sorterad. Vi enkelhetens skull betecknar vi antalet lagrade element med n (det är alltså a.size()). De redan lagrade värdena finns på index 0 till n-1

Det nya elementet ska alltså få ett index mellan 0 och n. Om vi vet vilket index i det nya elementet ska placeras på kan vi använda metoden add(i, x) för att lägga in det.

Om vi börjar från vänster (index i = 0) och letar så är det två villkor som säger att vi inte funnit platsen än:

1.   i < n   och
2.   x > a_i

Om något av villkoren inte är uppfyllt har vi funnit platsen. Det kan vara först som fall (a), någonstans inuti som fall (b) eller efter sista lagrade elementet som fall (c).

1. Vi behöver inga specialfall. Algoritmen fungerar även för en från början tom arraylist (om a.size() == 0 ) liksom att det nya elementet ska in efter alla lagrade element.
2. Ordningen mellan villkoren i while-satsen är väsentlig. Om i == a.size() är det illegalt att göra a.get(i) (ger ett index out of bounds exception). Java-språket är dock konstruerat så att om sanningsvärdet kan bestämmas utifrån det första villkoret i ett and- eller or-uttryck så undersöks inte det andra villkoret.

I ovanstående sortering utnyttjade vi egenskapen att det går att lägga in ett nytt element var som helst i en arraylist. Arraylister är implementerade med hjälp av arrayer. Operationen a.add(i,x) innebär att elementen från och med plats i och uppåt måste flytta ett steg. Detta sköts internt av arraylist-koden.

Vi ska här studera hur man kan göra en instickssortering på plats i en array. Vi ska alltså inte skapa en ny array utan ordna om värdena i den givna arrayen så att den blir sorterd.

Antag att vi från början har denna osorterade array:

Vi delar in arrayen i två delar: den vänstra delen som innehåller sorterade element och den högra delen med osorterade element. Från början innehåller den vänstra delen bara ett element:

Idéen i algoritmen är att successivt utöka den sorterade med ett element åt gången genom att infoga det första av de osorterade bland de sorterade så att dessa förblir sorterade.

Observera att de element som finns på plats 0 - 4 är precis samma element som fanns på plats 0 - 4 från början men att de nu är sorterade.

Vi ska nu titta på hur det går till att utvidga den sorterade delen skall inkludera talet 9 (elementet på plats 5).

Vi börjar med att kopiera talet 9 till en annan variabel. Platsen 5 blir då "ledig" även om talet 9 ligger kvar tills vi lagt något annat där:
Vi jämför sedan det uttagna talet med det som ligger på plats 4:
Eftersom 9 är mindre än 12 flyttar vi 12 till 9-ans gamla plats. Plats 4 blir då ledig.
Vi jämför sedan 9 med talet på plats 3:
Eftersom 9 är även är mindre än 11 flyttar vi 11 till plats 4:
Jämför talet 9 med elementet på plats 2:
Eftersom 9 är större än 8 har vi hittat platsen för talet 9. Lägg in det:

Efter dessa steg är den sorterade delen utvidgad till att omfatta elementen 0 till 5.

Observera att algoritmen fungerar om x skulle råka vara större än talet på plats i-1. Om däremot x är minst dvs mindre är a[0] så kommer vi få ett negativt index. För att hantera det måste vi kontroller att j inte är negativt innan vi jämför a[j] med x:

För att göra en fullständig sortering låter vi i löpa från ett till det högsta indexet. Vi förpackar algoritmen i en metod där vi skickar arrayen och antalet använda element som parametrar.

Vi har valt att skicka med antalet element som ska sorteras som en parameter. Metoden blir då mer flexibel än om vi låter metoden använda a.length. Om vi således önskar en hel array sorterad anropar vi med insertionSort(a, a.length).

Instickssorteringen hör till gruppen "enkla sorteringsalgoritmer". Andra algoritmer i den gruppen är urvalssortering och bubbelsortering. Alla dessa karakteriseras av att tiden växer proportionellt mot kvadraten på antalet element.

Övning: Gruppen AlgoRythmics illustrerar metoden så här. Den är dock aningen annorlunda implementerad. Skriv om koden så att den exakt följer deras implementation!

Gruppen "avancerade sorteringsalgoritmer" innehåller bl. a. mergesort, quicksort och heapsort. För dessa växer tiden typiskt proportionellt mot   n·log(n)   som är en betydande förbättring mot   n²  för stora värden på n (antalet element som ska sorteras).

Om en array är sorterad går det att mycket effektivt om ett visst värde finns med eller ej. Idéen är mycket enkel:

Eftersom antalet element att söka bland halveras varje steg blir arbetet proportionellt mot log₂ n där n är antalet element att söka bland. Således krävs det ca 10 försök att leta bland 1000 element och 20 försök att leta bland 1 000 000.

Även om idéen är enkel så är implementationen inte alldeles trivial. Här är en version:

1. Om det sökta värdet x finns i arrayen måste dess index i uppfylla relationen 0 ≤ i < n.
2. Omedelbart före while-loopen gäller således att low ≤ i < high
3. I loopen ändras low eller high på ett sätt så att relationen low ≤ i < high bevaras. Man säger att relationen är en loop-invariant.
4. Så länge som loop-villkoret är sant kommer relationen low < mid < high vara uppfylld. Det betyder att intervallet som vi söker i hela tiden blir kortare. Loopen kommer således att avbrytas.
5. När loopen stannat är low ≥ high + 1