Sortering

Den här listan med namn är inte i ordning:

namn = ['Torvalds', 'Zuckerberg', 'Lovelace', 'Turing', 'Johnson']

Men om vi vill skriva ut den i ordning? Då behöver vi sortera listan, det kan vi göra såhär:

print(sorted(namn))

Men det är ingen magi bakom den här sorted-funktionen. I det här avsnittet ska vi bygga den själva.

En sorteringsalgoritm

En algoritm är en lista instruktioner som ska utföras för att uppnå ett visst mål eller producera ett visst resultat - precis som ett recept för att baka en kaka. När vi programmerar förklarar vi dessa steg på ett språk som maskiner förstår.

Vår lista med namn är färdigsorterad när alla namn står i alfabetisk ordning. Vi vet om ett namn ska komma före ett annat genom att jämföra dem med mindre än (\(<\)) eller större än (\(>\)):

print('Lovelace' < 'Turing') 

print('Turing' > 'Lovelace')

Båda rader skriver ut “True” - för Lovelace (som börjar på L) borde komma före Turing (som börjar på T). 

Vårt mål är att få hela listan i ordning, men hur kommer vi dit? Även om vi själva kan skriva namn i bokstavsordning är det klurigt att förklara för en dator exakt hur den ska göra.

Alla steg som ska utföras för att nå vårt mål, en sorterad lista, utgör en sorteringsalgoritm. Det finns jättemånga, med olika för- och nackdelar. Här ska vi titta på en som heter Bubblesort:

Idén är såhär:

• Välj två namn bredvid varandra.
• Om de är i fel ordning, byt plats på dem.

Efter det så kommer ju listan vara lite bättre uppordnad än innan. Om vi gör detta tillräckligt många gånger kommer sedan hela listan vara sorterad.

Bubblesort i Python

Såhär skulle vi kunna göra det ovanstående i Python:

# Gå igenom listan från start till slut med hjälp av en for-loop
# Jämför namn på plats I med det som kommer efter
# Om de är I fel ordning, byt plats på dem

Det kan vi skriva såhär:

Jämför den första utskriften och den andra, du kan se att den är lite mer sorterad än innan!

Det enda som saknas är att köra for-loopen flera gånger, för att successivt få en mer och mer sorterad lista. Vi kan få tillräckligt många omgångar genom att lägga den i en annan for-loop.

Det slutliga programmet ser ut såhär:

namn = ['Torvalds', 'Zuckerberg', 'Lovelace', 'Turing', 'Johnson'] 

print("Osorterad version:") 
print(namn) 

for j in range(0, len(namn)): 
    for i in range(0, len(namn) - 1): 
        if namn[i+1] < namn[i]: 
            namn[i], namn[i+1] = namn[i+1], namn[i] 

print("Sorterad version:") 
print(namn)