Introduktion till programmering, del 9- Listor och sortering

Onsdag mitt i veckan! Nästan i alla fall. Hur som helst, dags för Introduktion till programmering!

Förra veckan tittade vi lite mer på objekt och avancerade datatyper. Idag ska vi titta på sortering!

Ibland kanske man har en godtycklig lista av objekt, och vill sortera dessa. Om det är heltal kanske man vill ha dem i storleksordning, är det strängar kanske man vill sortera dem i bokstavsordning.

Det finns såklart flera olika sätt att sortera också, men vilket är bäst? Kuggfråga! Det beror lite på vad man sorterar och hur många element som finns i listan! Först och främst ska vi kort gå igenom listor och hur man använder dem.

Listor

En lista är en följd objekt, och i Pythons fall av godtycklig typ. Med andra ord skulle man kunna ha en lista med både heltal, strängar och objekt, eller så kan man ha en lista som alla innehåller samma datatyp (t.ex. heltal).

Vi kommer i detta inlägg gå igenom listor med heltal. Om vi vill skapa en lista med heltalen 1,2 och 3 skriver vi:

lista = [1, 2, 3]

Det går också att skriva:

lista = range(1, 4)

För att hämta ut ett värde ur en lista skriver man lista[x] där x är det nummer i listan man vill hämta ut. Värt att nämna är att räknaren börjar på 0, så vill man i exemplet ovan hämta ut talet 3 måste man alltså skriva lista[2], där 2 kännetecknar den tredje positionen i listan. Hur vet man då, i exempelvis en loop, vilke

Olika sorteringsalgoritmer

Gemensamt för alla sorteringsalgoritmer är att man på något sätt traverserar listan med objekt, jämför dem mot varandra, och byter plats på dem när jämförelsen ger ett visst utfall. Oftast traverseras listan flera gånger, som t.ex. när man använder “Bubble Sort”, som börjar från början av listan, jämför två tal åt gången och byter plats på dem om det första är större än det andra (finns bra förklaring på Wikipedia-länken). Detta gör att efter varje iteration fastställer man ett av talen på sin rätta position i listan. Här är ett exempel på en Bubble Sort skriven i Python:

# -*- coding: cp1252 -*-

def bubbleSort (unsortedList):

 # Osorterad i början
 isSorted = False
 while not isSorted:
     
  # Antar att listan är sorterad varje iteration
  isSorted = True
  
  for element in range(0, len(unsortedList)-1): 
   if unsortedList[element] > unsortedList[element+1]:
       
    # Listan var visst inte sorterad...
    isSorted = False
    tempElement = unsortedList[element+1]
    unsortedList[element+1] = unsortedList[element]
    unsortedList[element] = tempElement

  print(str(unsortedList))

Vi har här några nya begrepp jag tänkte ta upp innan vi går vidare (och lite repetition på gammalt skadar inte heller, eller hur?).

Hela härligheten körs i en while-loop med villkoret “not isSorted” (not används för att negera ett uttryck, dvs omvandla True till False och vice versa). Varje nytt varv antar vi att listan är sorterad, och hittar vi några tal som ska byta plats konstaterar vi att listan inte är sorterad, vilket garanterar minst ett varv till i loopen.

Den inre for-loopen ser lite konstig ut, vad händer där? Jo, först skapas en lista med range(). Denna lista går från 0 till len(unsortedList)-1. Detta innebär längden på vår lista minus ett. Detta eftersom programmeringsspråk ofta betraktar “0” som det första elementet i listan, och len() returnerar antalet objekt i listan. “for element in…”, då, vad betyder det? Jo, vi har definierat för vilka tal vi vill köra loopen, men vi sätter också namnet “element” på dem, så att vi i varje iteration kan referera till det nuvarande talet!

Det som sedan händer är inte så konstigt. Vi sätter “isSorted” till False, eftersom vi upptäckt att listan inte är färdigsorterad. :O

Byta plats på värden

Att byta plats på två värden i listan är inte helt trivialt. Man kan inte bara sätta lista[0] = lista[1], för då skrivs det ursprungliga värdet i lista[0] över vilket kommer resultera i att båda positionerna har samma värde.

Istället får man använda sig av en temporär variabel, som t.ex. “tempElement” ovan, som man sätter till ett av värdena. Därefter kan man skriva över det värdet med det andra, och avslutningsvis lägga in värdet på tempElement över det andra värdet. Här är en illustration över hur det fungerar i praktiken:

 

Det var allt för denna vecka, hoppas ni lärt er hur Bubble Sort fungerar!

Nästa vecka kommer vi fortsätta med sortering, men vi kommer titta på en vackrare algoritm som fungerar på ett helt annat sätt! Spännande va!? 😉