MAA11 Algoritmit ja lukuteoria

Järjestämisalgoritmit

Pythonin listassa on metodi sort, joka järjestää listan alkiot pienimmästä suurimpaan. Metodia voidaan käyttää vaikkapa näin:

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

Ohjelma tuottaa seuraavan tuloksen:

[1, 2, 3, 5, 8]

Metodi sort on kätevä, mutta kuinka voisimme järjestää listan itse?

Kuplajärjestäminen

Oletamme seuraavaksi, että järjestettävänä on lista jossa on n alkiota. Perinteinen yksinkertainen järjestämisalgoritmi on kuplajärjestäminen, joka muodostuu kahdesta silmukasta. Ensimmäinen silmukka suorittaa n kierrosta ja toinen silmukka käy läpi listan luvut vasemmalta oikealle. Aina jos vierekkäin on kaksi alkiota, joista vasen on suurempi kuin oikea, algoritmi vaihtaa näiden alkioiden järjestyksen. Algoritmi voidaan toteuttaa näin:

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)

Ohjelma tuottaa seuraavan tuloksen:

[1, 2, 3, 5, 8]

Kuplajärjestäminen toimii, koska ensimmäisen kierroksen jälkeen listan suurin alkio on oikealla paikallaan, toisen kierroksen jälkeen myös toiseksi suurin alkio on oikealla paikallaan, jne. Niinpä n kierroksen jälkeen koko lista on järjestyksessä.

Algoritmin toiminta

Paremman kuvan järjestämisalgoritmin toiminnasta saa tulostamalla alussa ja jokaisen muutoksen jälkeen listan sisällön:

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)

Tästä näkee, että kuplajärjestäminen vaihtaa alkioita näin:

[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]

Suuret alkiot siis "kuplivat" kohti listan loppuosaa, kunnes lista on järjestyksessä.

Algoritmin tehokkuus

Järjestämisalgoritmin tehokkuutta voidaan mitata sen perusteella, montako vertailua algoritmi suorittaa. Voimme mitata kuplajärjestämisen tehokkuuden näin:

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

laskuri = 0

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

print(laskuri)

Ohjelma tuottaa seuraavan tuloksen:

20

Tässä ideana on, että muuttuja laskuri on alussa 0 ja kasvaa aina yhdellä, kun algoritmi vertailee kahta alkiota. Tässä tapauksessa algoritmi suorittaa yhteensä 20 vertailua.

Algoritmin vertailujen määrä voidaan laskea myös matemaattisesti: koska ensimmäinen silmukka suorittaa n kierrosta ja toinen silmukka suorittaa n–1 kierrosta, vertailujen määrä on aina n·(n–1). Esimerkiksi kun n = 5, vertailujen määrä on 5·4 = 20.

---

Tehtävä 1 Ratkaisematon

Tarkastellaan seuraavaa listaa, jossa on luvut 1–50 satunnaisessa järjestyksessä:

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]

Tee ohjelma, joka tulostaa, montako vertailua kuplajärjestäminen suorittaa tässä listassa.

Kirjoita ohjelma tähän:

---

Tehtävä 2 Ratkaisematon

Toinen yksinkertainen järjestämisalgoritmi on lisäysjärjestäminen, jossa ensimmäinen silmukka käy läpi listan alkiot vasemmalta oikealle. Jokaisen alkion kohdalla toinen silmukka siirtää alkion oikealle paikalleen listan alkuosassa vertaamalla alkiota ja vierekkäistä alkiota vasemmalla. Jos vasen alkio on suurempi, alkiot vaihdetaan keskenään, ja muuten silmukka päättyy. Algoritmi voidaan toteuttaa näin:

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

Tee ohjelma, joka näyttää, miten lisäysjärjestäminen järjestää listan [5, 2, 3, 8, 1]. Tulosta listan sisältö algoritmin alussa ja jokaisen muutoksen jälkeen.

Kirjoita ohjelma tähän:

---

Tehtävä 3 Ratkaisematon

Kuplajärjestämisessä vertailujen määrä riippuu suoraan listan alkioiden määrästä (n), mutta lisäysjärjestämisessä myös listan sisältö vaikuttaa.

Tee ohjelma, joka tulostaa, montako alkioiden vertailua lisäysjärjestäminen suorittaa tehtävän 1 listassa.

Kirjoita ohjelma tähän:

---

Tehtävä 4 Ratkaisematon

Kuplajärjestämistä voidaan tehostaa niin, että jos sisemmän silmukan aikana ei tule yhtään muutosta, algoritmi lopetetaan, koska lista on silloin järjestyksessä.

Tee ohjelma, joka tulostaa, montako alkioiden vertailua tehostettu kuplajärjestäminen suorittaa tehtävän 1 listassa.

Kirjoita ohjelma tähän:

---