MAA11 Algoritmer och talteori

Sorteringsalgoritmer

I Pythons lista finns metoden sort, som sorterar listans element från minsta till största. Metoden kan till exempel användas så här:

lista = [5, 2, 3, 8, 1]
lista.sort()
print(lista)

Programmet producerar följande resultat:

[1, 2, 3, 5, 8]

Metoden sort är behändig, men hur kan vi sortera listan själva?

Bubbelsortering

Vi antar att vi har en lista med n element som ska sorteras. En traditionell, enkel sorteringsalgoritm är bubbelsortering, som bildas av två loopar. Den första loopen utför n varv och den andra loopen går igenom listans tal från vänster till höger. Alltid när två element står bredvid varandra varav det vänstra är större än det högra, ändrar algoritmen ordningen på dessa element. Algoritmen kan genomföras så här:

lista = [5, 2, 3, 8, 1]
n = len(lista)

for i in range(n):
    for j in range(n-1):
        if lista[j] > lista[j+1]:
            t = lista[j]
            lista[j] = lista[j+1]
            lista[j+1] = t

print(lista)

Programmet producerar följande resultat:

[1, 2, 3, 5, 8]

Bubbelsortering fungerar, eftersom listans största element är på rätt plats efter det första varvet, efter det andra varvet är även det näst största elementet på rätt plats, osv. På så sätt är hela listan sorterad efter n varv.

Algoritmens funktion

En bättre bild av sorteringsalgoritmens funktion fås genom att skriva ut listans innehåll i början och efter varje ändring:

lista = [5, 2, 3, 8, 1]
print(lista)
n = len(lista)

for i in range(n):
    for j in range(n-1):
        if lista[j] > lista[j+1]:
            t = lista[j]
            lista[j] = lista[j+1]
            lista[j+1] = t
            print(lista)

Här ser man att bubbelsortering byter elementen på detta vis:

[5, 2, 3, 8, 1]
[2, 5, 3, 8, 1]
[2, 3, 5, 8, 1]
[2, 3, 5, 1, 8]
[2, 3, 1, 5, 8]
[2, 1, 3, 5, 8]
[1, 2, 3, 5, 8]

Stora element ”bubblar” alltså mot slutet av listan, tills listan är sorterad.

Algoritmens effektivitet

Sorteringsalgoritmens effektivitet kan mätas utgående från hur många jämförelser algoritmen utför. Vi kan mäta bubbelalgoritmens effektivitet så här:

lista = [5, 2, 3, 8, 1]
n = len(lista)

raknare = 0

for i in range(n):
    for j in range(n-1):
        raknare += 1
        if lista[j] > lista[j+1]:
            t = lista[j]
            lista[j] = lista[j+1]
            lista[j+1] = t

print(raknare)

Programmet producerar följande resultat:

20

Idén här är att variabeln raknare i början är 0 och växer alltid med ett, när algoritmen jämför två element. I detta fall utför algoritmen sammanlagt 20 jämförelser.

Antalet jämförelser som algoritmen utför kan även beräknas matematiskt: eftersom den första loopen utför n varv och den andra loopen utför n–1 varv, är antalet varv alltid n·(n–1). Exempelvis när n = 5, är antalet jämförelser 5·4 = 20.

---

Uppgift 1 Olöst

Vi granskar följande lista, där talen 1–50 är i slumpmässig ordning:

lista = [32, 18, 19, 25, 6, 47, 13, 49, 41, 1, 24, 15, 26, 5, 48, 21, 30, 50, 33, 9, 35, 2, 11, 20, 22, 40, 31, 45, 44, 12, 39, 3, 34, 7, 29, 10, 28, 42, 16, 23, 4, 17, 38, 27, 8, 43, 14, 46, 37, 36]

Gör ett program som skriver ut hur många jämförelser bubbelsortering utför i denna lista.

Skriv ditt program här:

---

Uppgift 2 Olöst

En annan enkel sorteringsalgoritm är insättningssortering, där den första loopen går igenom listans element från vänster till höger. Vid varje element flyttar den andra loopen elementet till sin rätta plats i början av listan genom att jämföra elementet med elementet till vänster. Om det vänstra elementet är större kan elementen bytas sinsemellan, annars stannar loopen. Algoritmen kan genomföras så här:

for i in range(n):
    for j in range(i,0,-1):
        if lista[j-1] > lista[j]:
            t = lista[j-1]
            lista[j-1] = lista[j]
            lista[j] = t
        else:
            break

Gör ett program som visar hur insättningssortering sorterar listan [5, 2, 3, 8, 1]. Skriv ut listans innehåll i början av algoritmen och efter varje förändring.

Skriv ditt program här:

---

Uppgift 3 Olöst

Vid bubbelsortering beror antalet jämförelser direkt på antalet (n) element i listan, men vid insättningssortering inverkar även listans innehåll.

Gör ett program som skriver ut hur många jämförelser av element insättningssortering utför i listan i uppgift 1.

Skriv ditt program här:

---

Uppgift 4 Olöst

Bubbelsortering kan effektiviseras så att om inga förändringar sker i den inre loopen avslutas algoritmen, eftersom listan då är i ordning.

Gör ett program som skriver ut hur många jämförelser av element effektiviserad bubbelsortering utför i listan i uppgift 1.

Skriv ditt program här:

---