Sortiranje elemenata liste

1. Uvod

Sortiranje niza je postupak kojim se elementi niza slažu po veličini. Problem sortiranja se često pojavljuje u programiranju, pa postoji više algoritama za njegovo rješavanje. Oni se razlikuju po složenosti i efikasnosti. Jednostavniji algoritmi su sasvim dobri za sortiranje nizova s manjim brojem elemenata (najviše nekoliko stotina), dok su za velike nizove potrebni nešto složeniji (merge sort, quick sort).  

2. Sortiranje zamjenom elemenata (eng. Selection sort)

Algoritam za sortiranje zamjenom je jedan od jednostavnijih algoritama. Efikasan je za nizove s manjim brojem elemenata (do 500).

Sortiranjem zamjenom se u prvom koraku, na prvo mjesto dovodi  najmanji broj, u drugom koraku se, na drugo mjesto dovodi  najmanji od preostalih itd. Postupak se nastavlja sve dok se ne dođe do potpuno sređenog niza.

I za ovaj algoritam postoji više inačica:

U prvoj inačici postupak zamjene napravi se svaki puta kada se pronađu dva elementa čije je poredak obratan od redoslijeda sortiranja, dok  se u drugoj, danas popularnijoj, najprije pronađe najmanji element i tek onda se izvrši postupak zamjene.

2.1. 1. inačica – Sortiranje zamjenom svakog neodgovarajućeg elementa

Vrijednost svakog element niza, počevši od prvog uspoređuje se s vrijednosti elemenata koji dolaze iza njega. Ako je poredak dva elementa koja se uspoređuju obratan od redoslijeda sortiranja, elementima se zamjene vrijednosti.

Algoritam za sortiranje na opisani način možemo zapisati ovako:

za i=1 do n-1 činiti
    za j=i+1 do n činiti

          ako je a[i]> a[j] onda
                                      zamjeni a[i] i a[j]

Podsjetimo se, zamjenu vrijednosti varijablama x i y moguće je napraviti na više načina. Dva su najčešća:

Uporabom računskih operacija zbrajanja i oduzimanja

Ako su na početku dane varijable x=6 i y=4, niz naredbi:

x = x + y
y = x - y
x = x - y 

daje vrijednosti x=4 i y=6

Pomoćnom varijablom

Ova metoda može se predočiti na sljedeći način: Na raspolaganju su dvije pune boce, jedna Cole, a druga Fante. Potrebno je sadržaj Cole presipati u bocu Fante, a Fantu preliti u bocu Cole. Jedini način je Colu presipati u pomoćnu posudu, preliti Fantu u bocu od Cole i na kraju Colu iz pomoćne posude preliti u bocu Fante! Taj princip primjenjuje se i za zamjenu varijabli.

Promotrimo:

Ako su na početku dane varijable x=6 i y=4, niz naredbi:

                t=x;    → vrijednost varijable x smješta se u pomoćnu varijablu t

                x=y;    → u varijablu x smješta se vrijednost varijable y, dakle x=4

                y=t;    → u varijablu y smješta se vrijednost pomoćne varijable t, dakle y=6

2.2. Zadatak 1

Zapiši prethodno opisani algoritam u Pythonu.

2.3. Zadatak 2

Što će se ispisati na zaslon monitora nakon izvođenja sljedećeg programa ako se prilikom unošenja podataka upišu sljedeće vrijednosti: n=8, a={4, 2, 7, -3, 15, 12, 8, -21}, m1=2, m2=7?

def upisi(x):

    for i in range (n):

        x[i]=int(input())

    return

def sortiraj(x):

    for i in range (m1-1,m2-1,1):

        for j in range (i+1,m2,1):

            if x[i]>x[j]:

                pom=x[i]

                x[i]=x[j]

                x[j]=pom

    return

def ispisi(x):

    for i in range (n):

        print (x[i])

    return

n=int(input('Unesi broj elemenata niza (<=10): '))

a=[0]*n

if 0<n<=10:

    print('Unesi elemente: ')

    upisi(a)

    m1=int(input('Od kojeg mjesta želiš krenuti?'))

    m2=int(input('Na kojem mjestu želiš završiti?'))

    sortiraj(a)

    print('Novodobiveni niz je:')

    ispisi(a)

else:

    print('Upisani broj nije u traženom rasponu.')

2.4. 2. inačica – Sortiranje izborom najmanjeg elementa

Prolazi se kroz niz i pronalazi se najmanji element u njemu. Kada se pronađe, zamjeni se s početnim. U sljedećem koraku prvi se element zanemari te se traži najmanji od preostalih koji se dovede na drugo mjesto…

za i=1 do n-1 činiti

{

      mjesto_min=i;

      za j=i+1 do n činiti

            ako je a[j]<a[mjesto_min] onda

                 zamjeni a[i] i a[mjesto_min]

}

2.5. Zadatak 3

Napravi program u kojem ćeš, primjenjujući prethodnu funkciju za sortiranje izborom najmanjeg elementa, sortirati uzlazno niz od 10 elemenata.

2.6. Zadatak 4 - funkcije min() i sort ()

Istraži način rada funkcija min() i sort(). Pokušaj ih primijeniti u  programu iz zadatka 3.

3. Sortiranje zamjenom susjednih elemenata (Metoda mjehurića, (eng. Bubble sort)

Ova metoda od prethodnih se razlikuje po tome što se u bubble sortu uspoređuju susjedne vrijednosti, a ne fiksira se jedan element čija se vrijednost tada uspoređuje s vrijednostima preostalih elemenata.

Uspoređivanje prestaje kada u prolasku kroz polje nije izvršena niti jedna zamjena. To znači da je niz sortiran. Zbog kontrole zamjene uvodi se pomoćna varijabla koja može biti brojčana ili logička. Njezina vrijednost mijenja se na početku svakog prolaska kroz polje na jednu vrijednost, a ako je napravljena bar jedna zamjena, pomoćna varijabla poprimit će drugu vrijednost. Prvi put kada se vrijednost kontrolne varijable ne promjeni tijekom prolaska kroz polje algoritam staje (polje je sortirano).

Zbog takvog načina uspoređivanja preporučuje se za sortiranje gotovo sortiranih nizova u kojima će uspoređivanje prestati istog trena kad je niz sortiran (za razliku od prethodne metode). To je također metoda koja se koristi za sortiranje nizova s manjim brojem elemenata.

Algoritam:

i=1

dok je (k<>0 ILI i==1) činiti

{

      k=0

      za j = 0 do n-i-1 činiti

            ako je a[j]>a[j+1]

            {

                  zamjeni vrijednosti varijablama a[j] i a[j+1]

                  k=1

            }

      i=i+1

}

3.1. Zadatak 1

Napravi funkciju za buuble sort u Pythonu. Funkciju primjeni za rješavanje sljedećeg problema:

Potrebno je bilježiti rezultate na natjecanju u skoku u dalj za svakog učenika jednog razreda. Program treba napraviti rang listu učenika s njihovim rezultatima.

4. Zadatci za vježbu

Zadatak 1. Napravi program koji omogućuje upisivanje bodova za svaki od 3 zadatka na natjecanju iz matematike za n (n<30) učenika. Program treba ispisati rang listu natjecatelja - redni broj natjecatelja i ukupan broj ostvarenih bodova.

Zadatak 2. Napravi program koji traži unošenje broja n (n<30), a nakon toga unošenje dva niza brojeva, svaki od po n elemenata. Program treba formirati treći niz tako da je i-ti element novog niza zbroj i-tih elemenata prva dva niza. Koristeći bilo koju od prethodno opisanih metoda, program nakon zbrajanja treba silazno poredati elemente dobivenog niza. Na zaslon treba ispisati novodobiveni niz u izvornom obliku i sortiran.

Primjerice,  ako je n=5, a = {1, 4, 2, 6, 3},   b = {12, 31, 17, 1, 8}, onda je c = {1+12, 4+31, 2+17, 6+1, 3+8}.

i na zaslonu trebaju biti prikazani nizovi: 13, 35, 19, 7, 11 i 35, 19, 13, 11, 7.

Zadatak 3. Napravi program koji će tražiti unošenje dva niza brojeva (prvi od n, a drugi od m elemenata, n, m<30). Program treba sortirati dane nizove, a zatim formirati treći niz koji se dobije spajanjem prethodno sortiranih nizova. Dobiveni niz također treba biti sortiran.

Napomena: prilikom rješavanja ovog zadatka primjeni metodu mjehurića.

Zadatak 4. Napravi program koji će za zadani pozitivan cijeli broj manji od 2 000 000 000, pronaći najveći mogući broj koji može biti formiran promjenom redoslijeda njegovih znamenki.

Primjerice, za broj 6859, traženi rezultat je 9865. 

5. Algoritmi sortiranja na internetu

Na internetu postoji velik broj videa koji se bave temom sortiranja. Primjerice:

Selection sort:

Bubble sort

Insertion sort