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?
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ä.
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ä.
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:
20Tä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.
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:
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: breakTee 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:
Tee ohjelma, joka tulostaa, montako alkioiden vertailua lisäysjärjestäminen suorittaa tehtävän 1 listassa.
Kirjoita ohjelma tähän:
Tee ohjelma, joka tulostaa, montako alkioiden vertailua tehostettu kuplajärjestäminen suorittaa tehtävän 1 listassa.
Kirjoita ohjelma tähän: