Sortiranje mehurićima (bubble sort)

Uradimo sada jedan primer algoritma za sortiranje niza brojeva koji se jako oslanja na enumerate funkciju.

Ovaj algoritam ima dve petlje, for petlju koja je ugnježdena unutar while petlje. Unutrašnja for petlja ima za zadatak da poredi redom parove brojeva, prvi sa drugim, drugi sa trećim sve do pretposlednjeg sa poslednjim. U donjem primeru, u listi niz =[6, 5, 3, 1, 8, 7, 2, 4] dolazi prvo do poređenja brojeva 6 i 5. Pošto sortiramo u rastućem poretku dolazi do zamene mesta brojeva 6 i 5. Sada je na prvom mestu 5, a na drugom 6. Sada se poredi 6 sa sledećim brojem, koji je 3 i opet dolazi do zamene. Unutrašnja for petlja se završava kada smo proverili sve susedne parove.

Posle prvog prolaza raspored je sledeći [5, 3, 1, 6, 7, 2, 4, 8]. Ova lista očigledno nije sortirana, samo je malo bolje uređena. Stoga se ulazi u novu iteraciju while petlje koja još jednom pokreće for petlju koja poredi parove. Iz spoljne petlje se izlazi kada nije došlo ni do jedne zamene tokom prolaza. Na donjoj animaciji možemo videti faze ovog algoritma za zadati niz.

  
niz =[ 6, 5, 3, 1, 8, 7, 2, 4] #Proizvoljni niz

ima_zamene=True#Govori nam da li je u prolazu došlo do zamene elemenata
n=len(niz)-1 #Ovo je zapravo zadnji indeks niza, u našem primeru 4

while(ima_zamene):
    # Pretpostavljamo da je niz već sortiran
    ima_zamene=False 
    """Isecamo poslednji element iz niza, jer unutar petlje
    proveravamo naredni preko indeks + 1"""
    for indeks,br in enumerate(niz[0:n]): 
        if niz[indeks]>niz[indeks+1]:
            #Zamenjujemo elemente na mestima indeks i indeks+1
            niz[indeks],niz[indeks+1]=niz[indeks+1],niz[indeks]
            ima_zamene = True
else:
    print (niz)

				
Kopiraj
slika

Zadatak: Napraviti funkciju koja ispisuje sve proste brojeve manje od 200. Mala pomoć: prost broj možemo da gledamo kao onaj koji nije deljiv ni sa jednim prethodnim brojem osim sa 1


Zip

Za sam kraj ovog kursa o petljama pogledajmo vrlo korisnu zip funkciju. Ona nam omogućava da istovremeno vršimo iteraciju kroz dve ili više lista. Napravimo program koji upoređuje paralelno elemente dva niza i ispisuje veći od njih

  
niz1 = [23,4,53,2,12,32,12,6]
niz2 = [3,15,105,22]

for x,y in zip(niz1,niz2):
    if x>=y:
        print (x),
    else: print (y),
            
Kopiraj

Možemo primetiti da se for petlja se zaustavlja kod kraće od dve liste. Slično važi i za rečnike i stringove.

Zadatak: Iskoristiti znanje o funkciji range() i zip() kako bi se izbegla funkcija enumerate() pri numerisanju reči po izboru.