Introduktion till programmering, del 10- Mer sortering

Onsdag, onsdag, onsdag, lillonsdag (och så vidare)!

Förra veckan tittade vi på listor och sortering med Bubble sort-algoritmen, i detta avsnitt ska vi titta vidare på sortering men med en lite annan approach, “Quicksort”-algoritmen.
Quicksort fungerar helt annorlunda än Bubble sort. Det första som händer är att man väljer ut en slumpmässig “pivot” bland talen i listan. Sedan skapar man två underlistor, där man placerar alla tal som är större respektive mindre än pivot-talet.
När man gått igenom hela listan, gör man om proceduren för underlistorna tills alla tal är sorterade.
Med Bubble Sort vet vi inte när listan är färdigsorterad utan att gå igenom hela listan ytterligare en gång, men med Quicksort är det enklare. Varje gång man går ner till nästa steg i sorteringen vet man att pivoten är på rätt ställe (i mitten, i princip), och när man nått listlängden 1 är sorteringen klar.
Här är en illustration som visar ungefär hur Quicksort fungerar:

Det faktum att vi alltid går vidare med underlistorna i varje beräkningssteg, gör att detta är ett ypperligt tillfälle att använda oss av rekursion!
Vi skapar helt enkelt en rekursiv funktion, som tar en lista med tal, väljer ut en pivot, skapar två underlistor innehållande de större respektive mindre talen i förhållande till pivoten, och anropar funktionen rekursivt TVÅ gånger, en för varje lista.
Vad klurigt, va? Hur ska man då se till att man i slutändan får det resultat man vill ha? Hur lagrar man pivoten från varje steg? Särskilt när beräkningen delas upp i ett “binärt träd” i varje steg?

Jo, vi använder oss av “+”. Listor kan läggas ihop, precis som tal eller strängar! Den anropas från en lista, med en annan lista som argument (t.ex. lista1.extend(lista2)) och lägger då ihop dem.

Exempel:

list1 = [0, 1]
list2 = [2, 3]

>>>list1 + list2
[0, 1, 2, 3]

På detta sätt kan vi i varje steg säga att vi vill lägga ihop de lägre talen, pivoten, och de högre talen och eftersom vi vet att ingenting returneras förrän alla inre beräkningar är slutförda kommer vi få tillbaka den färdigsorterade listan.

Hur gör vi då för att beräkna vilka tal som är större respektive mindre än pivoten? Man skulle kunna göra en loop:

for element in range(len(unsortedList)):
 if element != pivot:
  if unsortedList[element] > unsortedList[pivot]:
   larger.append(unsortedList[element])
  else:
   smaller.append(unsortedList[element])

Men det här ser inte så roligt ut, och blir flera rader! Usch! Vi gör så här istället:

lesser = [x for x in list if x < pivot]
greater =[x for x in list if x >= pivot]

Mycket smidigare! Men vad händer egentligen här? Jo, vi säger att vi vill ha två listor. En ska innehålla alla x för vilka villkoret “x < pivot” gäller. Den andra ska innehålla alla x för villkoret “x >= pivot”.

Nu ska vi se hur hela funktionen ser ut:

def quicksort(unsorted):
 if unsorted == []: 
  return []
 else:
  pivot = unsorted[randint(0, len(unsorted)-1)]
  unsorted.remove(pivot)
  #print("Pivot: "+str(pivot)+", list: "+str(unsorted))
  lesser = quicksort([x for x in unsorted if x < pivot])
  greater = quicksort([x for x in unsorted if x >= pivot])
  return lesser + [pivot] + greater

Inte så omfattande, eller hur? Det första “if”-villkoret kontrollerar så att man inte skickar in en tom lista, för då vill vi inte göra någonting.

Sedan hämtas en pivot, som följdaktligen plockas bort ur listan. Därefter en utkommenterad utskriftsrad som skriver ut pivoten och listan, och sen skapas de “halvsorterade” listorna som på samma gång sorteras vidare rekursivt.

Sist av allt slås listorna ihop och returneras!

Är detta det mest effektiva sättet, beräkningsmässigt? Kanske inte!

Varför vill man förresten välja en pivot slumpmässigt? Kan man inte ta det första talet i listan varje gång? Jo, det kan man, men om man alltid väljer samma pivot är algoritmen inte lika effektiv i vissa enstaka fall.
Tänk till exempel om vi alltid väljer första talet till pivot, och får in listan [1, 2, 3, 4, 5, 6, 7, 8]. För att upptäcka att den här listan redan är sorterad skulle vi behöva gå igenom algoritmen inte mindre än 8 gånger.
Om vi däremot hade använt Bubble sort till den här listan, hade det räckt att köra algoritmen ett varv för att bli färdig.

För att veta vilka sorteringsalgoritmer som är bra på vad finns olika matematiska benämningar som jag inte tänkte gå in närmare på, här finns en lista över olika sorteringsalgoritmer och dess prestanda.
Detta betyder ju också, att man kan kombinera olika sorteringsalgoritmer för att få effektivast möjliga sortering. Exempelvis Quicksort för listor större än 10 tal, och bubble sort för listor mindre än 10 tal.

Men om man vill sortera annat då?

Att sortera heltal är enkelt, datorn har ju redan funktioner inbyggda för att jämföra sådana. Men om man vill sortera till exempel strängar, hur gör man då?
Svaret är att man gör på ungefär samma sätt, men an får använda andra jämförelsefunktioner. För strängar skulle man kunna jämföra ASCII-värdet för första bokstaven i strängen, för att sortera på bokstav.
Men som med så mycket annat finns det inget som säger hur man måste göra, så det står var och en fritt att skriva sina egna jämförelsefunktioner!

Det var allt för denna gång! Nästa vecka blir det inte så mycket kod, men vi kommer diskutera hur man optimerar kod och några intressanta exempel på varför man bör göra det! Håll ut 😉