Göm menyn

Algoritmer

Introduktion

Under detta avsnitt så ska vi ta en titt på ett antal vedertagna algoritmer, framförallt sorteringsalgoritmer.

Selection sort

Informell beskrivning

Antag att vi har en hög med kort som vardera har ett heltal på framsidan. Högen är blandad och vår uppgift är att sortera dem i stigande ordning. Detta kan vi göra så här:

  1. Gå igenom högen och hitta kortet med det minsta talet
  2. Flytta detta kort till början av högen
  3. Upprepa steg 1 och 2 till dess att vi gått igenom alla kort

Illustration

Selection sort 1 Selection sort 2 Selection sort 3 Selection sort 4 Selection sort 5

Implementation

Som vi ser nedan så kan detta göras på två olika sätt. Båda funktionerna är destruktiva även om den första endast är destruktiv i den mening att den osorterade listan blir överskriven. Den andra funktionen förstör orginallistan fullständigt (det blir tomma listan efter det körs), något som kan vara bra att ha i åtanke.

Insertion sort

Informell beskrivning

Antag att vi har en hög med kort som vardera har ett heltal på framsidan. Högen är blandad och vår uppgift är att sortera dem i stigande ordning. Dettta kan vi göra så här:

  1. Dela upp högen i två delar: en del som innehåller det första kortet (som vi anser är en sorterad hög) och en del som innehåller resten.
  2. Ta det översta kortet i resten och sortera in det på rätt plats i den sorterade högen.
  3. Upprepa steg 1 och 2 till dess att vi gått igenom alla kort

Illustration

Insertion sort 1 Insertion sort 2 Insertion sort 3 Insertion sort 4 Insertion sort 5 Insertion sort 6

Implementation

Precis som med selection sort så kan detta göras på två sätt; antingen så sorterar vi i samma lista som vi fick in (inplace), eller så skapar vi en ny resultat lista (copy).

Rekursiva algoritmer

Som ni kanske har märkt tidigare så kan den rekursiva implementation ofta vara kortare och mer "elegant" än den iterativa. Men det finns också problem som lämpar sig särskilt bra att lösa rekursivt. Givet ett problem försöker man först lösa ett mindre problem (reskurisvt) för att sedan utöka denna lösning till att gälla hela problemet. Denna metod kan ge upphov till mycket effektiva algoritmer.

Som första illustrerande exempel ska vi skapa en funktion anagrams som givet en sträng producerar en lista med alla anagram, det vill säga alla strängar som innehåller samma bokstäver i alla möjliga ordningar.

Induktiv metod

Induktiv metod

Anagramproblemets lösning

Tornet i Hanoi

Hanoi

Tornet i Hanoi är ett klassiskt problem inom datavetenskap. Spelet går ut på att flytta samtliga skrivor från den första pinnen till den sista utifrån några regler för förflyttning.

  • Endast en skiva i taget får flyttas
  • Skivorna får inte läggas åt sidan utan måste placeras på en av de tre pinnarna
  • En större skiva får aldrig placeras ovanpå en mindre skiva

Flytta torn med 1 skiva från A till C:

  • Flytta skivan från A till C

Flytta torn med 2 skivor från A till C med B som mellanlagring:

  • Flytta en skiva från A till B
  • Flytta en skiva från A till C
  • Flytta en skiva från B till C

Flytta ett torn med 3 skivor från A till C med B som mellanlagring:

  • Flytta ett torn med 2 skivor från A till B med C som mellanlagring
  • Flytta en skiva från A till C
  • Flytta ett torn med 2 skivor från B till C med A som mellanlagring

Implementation

Utifrån detta kan vi se ett mönster, mer generellt så gäller:

Flytta ett torn med n skivor från x till z med y som mellanlagring:

  • Om n = 1
    1. Flytta en skiva från x till z
  • Om n > 1
    1. Flytta ett torn med n -1 skivor från x till y med z som mellanlagring
    2. Flytta ett torn med 1 skiva från x till z med y som mellanlagring
    3. Flytta ett torn med n -1 skivor från y till z som mellanlagring

Lite om komplexitet

Algoritmen är mycket kort, men varje steg ger upphov till två rekursiva anrop med n - 1. Detta innebär att ett problem med n diskar kommer att kräva 2^n -1 antal steg, det vill säga problemet löses i exponentiell tid. Ett problem har 64 skivor kräver det inte mindre än 18446744073709551615 steg för att lösas.

Antal skivor Antal lösningssteg
1 1
2 3
3 7
4 15
5 31
6 63
7 127
8 255
9 511
10 1023

Quicksort

Informell beskrivning

Antag att vi har en hög med kort som vardera har ett heltal på framsidan. Högen är blandad och vår uppgift är att sortera dem i stigande ordning. Detta kan vi göra så här:

  • Välj ut ett kort som vi kallar pivotelement
  • Dela uppresten av högen i två delar: en som innehåller alla kort som är mindre än pivotelementet och en som innehåller alla som är större än eller lika med pivotelementet
  • Sortera varje hög för sig genom att köra algoritmen från början
  • Lägg ihop de sorterade högarna i rätt ordning med pivotelementet i mitten

Alt text

Vi kommer inte visa någon implementation av detta då det är en del av labb 7.


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2016-08-15