Python ja bubble sort

Bubble sort eli kuplasorttaus on hyvä keino opetella ymmärtämään sisäkkäisiä silmukoita. Kyseisellä menetelmällä on helppo myös visualisoida kuinka tämä yleinen algoritmi toimii. Kuplasorttausta on opetettu yleisti myös ohjelmoinnin opetuksen yhteydessä.

Wikipedia kertoo kuplalajittelusta seuraavaa:

Kuplalajittelu (engl. bubble sort) on erittäin hidas (O(n2)lajittelualgoritmi, jolla ei ole etuja nopeampiin algoritmeihin edes muistinkäytön suhteen.

Kuplalajittelun periaate:

  1. Periaatteena on käydä taulukon alkioita läpijärjestyksessä ja verrata tutkittavaa alkiota taulukossaseuraavana olevaan.
  2. Alkio, vaihdetaan näiden alkioiden paikkaa taulukossatoiseksi viimeisessä taulukon alkiossa.
  3. Ensimmäisen järjestyskierroksen jälkeen taulukko ei olevielä täysin lajiteltu. Järjestyskierroksia on oltava N-1,jossa N on taulukon alkioiden määrä.

Kuplalajittelu käytännössä

  1. Taulukon läpikäynnissä voi käyttää mitä tahansa
    toistolausetta
  2. Juokseva muuttuja i saa alkuarvon 0 ja tässä
    esimerkkitapauksessa loppuarvon 2

Tehdään oma versio siitä. Päätetään, että jokaisella kierroksella haetaan pienin luku käsiteltävän jonon alkuun eli käydään lista läpi siten, että ensimmäisellä kerralla käydään lista läpi ensimmäisestä viimeiseen alkioon ja etsitään pienin. Ja lähdetään kehittämään koodia paloissa.

def bubble(taulu):
    for i in range(len(taulu)):
        print(taulu[i:])
    print(taulu)
lista = [3,2,4,6,1,2,3,4,8]
print(lista)
bubble(lista)

Ja kun katsotaan tuon tulostusta, niin helpolla huomaa että laskuri menee yhden askeleen liian pitkälle eli tuo vertaisi viimeisellä kierroksella lukua itseensä. Asia on helppo korjata vähentämällä pituudesta yksi pois.

[3, 2, 4, 6, 1, 2, 3, 4, 8]
[2, 4, 6, 1, 2, 3, 4, 8]
[4, 6, 1, 2, 3, 4, 8]
[6, 1, 2, 3, 4, 8]
[1, 2, 3, 4, 8]
[2, 3, 4, 8]
[3, 4, 8]
[4, 8]
[8]

Ja sitten kehitetään koodia pienin baby stepein eteenpäin eli tehdään seuraavaksi silmukka, jolla vertaillaan arvopareja toisiin tai aluksi tulostetaan vain niiden indeksit:

def bubble(taulu):
    for i in range(len(taulu)-1):
        for j in range(i+1,len(taulu)):
             print(i,j, end = ” – ”)
    print(taulu)
lista = [3,2,4,6,1,2,3,4,8]
#print(lista)
bubble(lista)

Tulostus näyttää selvästi kuinka vertailu etenee eli mitä listan indeksejä verrataan toisiinsa.

0 1 – 0 2 – 0 3 – 0 4 – 0 5 – 0 6 – 0 7 – 0 8 –
1 2 – 1 3 – 1 4 – 1 5 – 1 6 – 1 7 – 1 8 –
2 3 – 2 4 – 2 5 – 2 6 – 2 7 – 2 8 –
3 4 – 3 5 – 3 6 – 3 7 – 3 8 –
4 5 – 4 6 – 4 7 – 4 8 –
5 6 – 5 7 – 5 8 –
6 7 – 6 8 –
7 8 –

Ja tuosta on nopea tehdä ns. arvojen swappaus eli mikäli jälkimmäinen arvo on pienempi kuin edellinen, niin vaihdetaan paikkoja. Arvojen vaihto keskenään tehdään yleisesti apumuuttujan avulla. Pythonissa sen kyllä voi tehdä monikon kautta.


                apu = taulu[i]
                taulu[i] = taulu[j]
                taulu[j] = apu
Ja sitten kokeillaan omaa koodia kokonaisuudessaan.
def bubble(taulu):
    for i in range(len(taulu)-1):
        print(taulu)
        for j in range(i+1,len(taulu)):
            if taulu[i] > taulu[j]:
                apu = taulu[i]
                taulu[i] = taulu[j]
                taulu[j] = apu
    print(laskuri)
    print(taulu)
lista = [3,2,4,6,1,2,3,4,8]
print(lista)
bubble(lista)
Koodi on oikeastaan melkoisen tehotonta. Kyseisen listan listan läpikäyminen vaatii 36 vaihetta eli suoritettavia käskyjä on kohtuuttoman paljon. Mutta ratkaisu toimii.
[3, 2, 4, 6, 1, 2, 3, 4, 8]
[1, 3, 4, 6, 2, 2, 3, 4, 8]
[1, 2, 4, 6, 3, 2, 3, 4, 8]
[1, 2, 2, 6, 4, 3, 3, 4, 8]
[1, 2, 2, 3, 6, 4, 3, 4, 8]
[1, 2, 2, 3, 3, 6, 4, 4, 8]
[1, 2, 2, 3, 3, 4, 6, 4, 8]
[1, 2, 2, 3, 3, 4, 4, 6, 8]

Käytännössä kuplasorttaus tehdään hiukan erilaisella periaatteella.  Tyypillinen ratkaisu kuplasorttaukselle on seuraava. Tuosta kannattaa tutustua silmukoiden kulkujärjestykseen.

def bubble(taulu):
    for i in range(len(taulu)-1,0,-1):
        print(taulu)
        for j in range(i-1):
            if  taulu[j] > taulu[j+1]:
                apu = taulu[j]
                taulu[j] = taulu[j+1]
                taulu[j+1] = apu;
    print(taulu)
lista = [3,2,4,6,1,2,3,4,8]
print(lista)
bubble(lista)

Ja koska tuolla on mukana ns. debug- lauseena ylimääräinen print- lause, niin helposti näkkee kuinka kuplasorttaus toimii käytännössä. Eli tulostus jokaisen silmukan jälkeen on seuraavanlainen ja tuosta näkee sorttauksen idean. Sorttaus kiertää 28 kertaa kahdessa eri silmukassa. Sorttaus on edelleen melkoisen tehotonta isoilla määrillä tietoa.

[3, 2, 4, 6, 1, 2, 3, 4, 8]
[3, 2, 4, 6, 1, 2, 3, 4, 8]
[2, 3, 4, 1, 2, 3, 4, 6, 8]
[2, 3, 1, 2, 3, 4, 4, 6, 8]
[2, 1, 2, 3, 3, 4, 4, 6, 8]
[1, 2, 2, 3, 3, 4, 4, 6, 8]
[1, 2, 2, 3, 3, 4, 4, 6, 8]
[1, 2, 2, 3, 3, 4, 4, 6, 8]
[1, 2, 2, 3, 3, 4, 4, 6, 8]
[1, 2, 2, 3, 3, 4, 4, 6, 8]

Yksi tapa opetella ohjelmointia on tehdä omia versioita yleisistä algoritmeistä. Pohtimalla ja kokeilemalla asioita oppii käyttämään erilaisia rakenteita ja miettimään myös koodin tehokkuutta. Ja kuplasorttaus on hyvä harjoittelukohde.

Tämä teksti on kirjoitettu ohjelmoinnin perusteiden ohjaamista varten eli tässä on vain näytetty kuinka tehottmasta koodista saa vielä tehottomampaa…

Kari…