Ponavljanje nastavnih sadržaja prethodnih razreda (5., 6., 7.)

Razmislimo: Zašto je važno sortirati stvari?
U svakodnevnom životu često se susrećemo s organiziranjem podataka. Zamislite ladicu s čarapama – kako biste najbrže pronašli odgovarajući par? Ako su čarape razbacane, traženje traje dugo. Ako su sortirane po bojama ili vrstama, posao je puno lakši. Ista stvar vrijedi za podatke – njihovo sortiranje štedi vrijeme, energiju i resurse.

U digitalnom svijetu sortiranje podataka ima mnoge primjene: od pretraživanja telefonskih brojeva, upravljanja financijama, organizacije fotografija do upravljanja zalihama u trgovinama. Ova lekcija pokazat će vam kako riješiti problem sortiranja kroz programiranje i algoritme.

Razvrstavanje (sortiranje) podataka

Zašto sortiramo podatke?
Sortiranje podataka omogućuje brže pretraživanje, analizu i upravljanje informacijama. Npr.:

  • u trgovini: organizacija proizvoda po cijeni ili kategorijama
  • u školi: evidencija učenika po prezimenima ili rezultatima
  • u financijama: analiza troškova prema veličini ili vrsti

Algoritmi sortiranja

Postoji više načina sortiranja, a danas ćemo naučiti osnovne principe. Kroz male zadatke shvatit ćemo kako možemo organizirati brojke prema veličini.

Sortiranje dva broja (Zadatak 1.)

Prvo ćemo naučiti kako zamijeniti mjesta dvaju brojeva. Primjenom Python programa, testirati ćemo logiku razvrstavanja:

  1. Ako je prvi broj veći od drugog, zamijenimo njihove vrijednosti.
  2. Prikazujemo rezultate.

Sortiranje tri broja (Zadatak 2.)

Sljedeći korak je razvrstavanje tri broja. Pomoću više uvjeta naučiti ćemo kako primijeniti algoritam sortiranja na više elemenata.

Objašnjenje zadatka sortiranja tri broja

Ponekad želimo poredati tri broja od najmanjeg do najvećeg. Kako bismo to učinili, možemo koristiti jednostavan postupak uspoređivanja i zamjene vrijednosti.

Što radimo u ovom zadatku?

  1. Zamislimo da imamo tri broja: a, b i c.
  2. Cilj nam je usporediti brojeve i, ako je potrebno, zamijeniti njihove pozicije tako da na kraju a bude najmanji broj, b bude srednji, a c najveći.

Kako to radimo?

  • Prvo uspoređujemo a i b. Ako je a veći od b, zamijenimo njihove vrijednosti.
  • Zatim uspoređujemo a i c. Ako je a veći od c, opet zamijenimo vrijednosti.
  • Na kraju uspoređujemo b i c. Ako je b veći od c, i ovdje zamijenimo njihove vrijednosti.

Što se događa u pozadini?

Postupak “zamjene” osigurava da:

  • Najmanji broj završi na početku (u a).
  • Najveći broj završi na kraju (u c).
  • Preostali broj, koji nije ni najmanji ni najveći, završi u sredini (b).

Vježba 1

  • Zadatak: Izmijenite računalno rješenje prethodnog zadatka tako da program sortira 3 broja prema veličini, od najvećeg prema najmanjem.

Sortiranje četiri broja

Kada želimo sortirati četiri broja (npr. a, b, c, d), postupak postaje malo složeniji jer moramo usporediti i zamijeniti više parova brojeva. Cilj je opet isti: na kraju poredati brojeve od najmanjeg do najvećeg.

Što ćemo raditi?

  • Proširit ćemo princip koji smo koristili za sortiranje tri broja.
  • Pomoću nekoliko usporedbi i zamjena osiguravamo da svaki broj završi na pravom mjestu.
  • Na kraju, a će biti najmanji, b će biti drugi po veličini, c treći, a d najveći.

Kako to radimo?

  1. Usporedi prvi i drugi broj (a i b). Ako je a veći, zamijeni ih.
  2. Usporedi prvi i treći broj (a i c). Ako je a veći, zamijeni ih.
  3. Usporedi prvi i četvrti broj (a i d). Ako je a veći, zamijeni ih.
  4. Sada je a sigurno najmanji broj.

Nastavljamo sortirati ostala tri broja:
5. Usporedi drugi i treći broj (b i c). Ako je b veći, zamijeni ih.
6. Usporedi drugi i četvrti broj (b i d). Ako je b veći, zamijeni ih.

Na kraju rješavamo posljednji par:
7. Usporedi treći i četvrti broj (c i d). Ako je c veći, zamijeni ih.

Nakon ovih koraka brojevi su sortirani od najmanjeg

Sortiranje tri broja pronalaženjem najmanjeg, srednjeg i najvećeg (Zadatak 3.)

Prikazat ćemo još jedan način sortiranja 3 broja koristeći se postupkom traženja najmanjeg ili najvećeg broja. Cilj je identificirati najmanji, najveći i srednji broj među tri zadana broja. Nakon toga ih ispisujemo redom od najmanjeg do najvećeg.

Pronalaženje najmanjeg broja:

  • Počinjemo tako da najmanjem broju (manji) pridružimo vrijednost a.
  • Uspoređujemo ga sa b i c. Ako je bilo koji od njih manji od manji, mijenjamo vrijednost varijable manji.

Pronalaženje najvećeg broja:

  • Najvećem broju (veci) pridružimo vrijednost a.
  • Uspoređujemo ga sa b i c. Ako je bilo koji od njih veći od veci, mijenjamo vrijednost varijable veci.

Pronalaženje srednjeg broja:

  • Srednji broj (srednji) izračunavamo tako da od ukupnog zbroja svih brojeva (a + b + c) oduzmemo manji i veci.

Što se događa s brojevima?

  • Ako unesemo a=9, b=1, c=4:
    • manji = 1
    • veci = 9
    • srednji = (9 + 1 + 4) - (1 + 9) = 4
  • Ispisuje se: 1, 4, 9 (sortirano od najmanjeg do najvećeg).

Vježba 2

  • Zadatak: Dogradite jedno od postojećih računalnih rješenja da program sortira 4 zadana broja počevši od najmanjeg.

Sortiranje nije samo nešto što koristimo u školi ili programiranju – to je praktična vještina koja ima primjenu u našem svakodnevnom životu. Danas smo naučili kako jednostavne odluke, poput uspoređivanja i zamjene brojeva, mogu pomoći u organizaciji podataka i rješavanju problema. No, zašto nam to znanje treba i gdje ga koristimo?
Zašto je ovo važno?
U bilo kojem poslu, razumijevanje kako organizirati podatke omogućit će ti da brzo rješavaš zadatke i štediš vrijeme.
U svakodnevnom životu:
– primjer ormara: kada sortiramo odjeću po sezoni, veličini ili boji, brzo nalazimo ono što nam treba
– primjer kupovine: kada tražimo najjeftiniji proizvod u trgovini, naš mozak zapravo sortira cijene
– primjer putovanja: kad organiziramo raspored ili rute, sortiramo aktivnosti prema vremenu ili udaljenosti
U školi i učenju:
– Sortiranje pomaže u organizaciji bilješki, planiranju obaveza i rješavanju zadataka.
– Primjer: Razvrstavanje ocjena u dnevniku omogućuje brzo prepoznavanje najboljeg ili najlošijeg rezultata.
U tehnologiji:
– Kada koristite Google pretraživanje, algoritmi sortiranja pomažu prikazati najvažnije rezultate na vrhu.
– U aplikacijama kao što su Excel ili kalkulacijski programi, sortiranje pomaže analizirati podatke, npr. popise učenika po prezimenima ili bodovima.
– U videovima ili fotografijama, često sortiraš po datumu, veličini ili imenu.
U budućnosti:
– Ako postaneš programer, znat ćeš stvoriti programe koji organiziraju podatke brzo i učinkovito.
– Ako se baviš financijama, moći ćeš analizirati troškove i prihode razvrstavanjem po kategorijama.

 

Algoritmi sortiranja nisu samo matematička vježba – oni nas uče logici, razmišljanju u koracima i traženju najboljeg rješenja za problem. Razumijevanje sortiranja pomaže vam razmišljati logično i strukturirano, što je korisno u bilo kojem području, bilo da želite biti liječnik, učitelj, inženjer ili vozač taksija koji optimizira svoje rute.

PROVJERI SVOJE ZNANJE

  1. Navedite tri primjera iz stvarnog života gdje sortiranje olakšava zadatak.
  2. Opiši svojim riječima zbog čega je potrebno sortirati podatke.
  3. Što znači sortiranje podataka prema silaznom redoslijedu?
  4. Opišite jedan postupak sortiranja 3 broja počevši od najmanjeg.
  5. Objasnite kako biste koristili algoritme sortiranja u organizaciji osobnih financija.

Sortiranje većeg broja podataka općenito je zanimljiv problem u programiranju i postoji nekoliko različitih pristupa kojima ga rješavamo. U sljedećoj ćemo se nastavnoj jedinici baviti algoritmima sortiranja većeg broja podataka.

Jeste li se ikada zapitali kako bi izgledao svijet bez reda? Zamislite da popis učenika u dnevniku nije abecedno složen ili da rezultati natjecanja nisu poredani od najboljeg do najlošijeg. Upravo sortiranje podataka čini naš svakodnevni život organiziranim i preglednim.

Sortiranje nije važno samo u svakodnevnom životu – ono je temelj brojnih računalnih aplikacija, od pretraživača interneta do organizacije podataka u velikim bazama. U ovoj lekciji naučit ćemo kako algoritmi za sortiranje funkcioniraju, kako ih možemo primijeniti u rješavanju stvarnih problema i zašto su neizostavan dio informatike.

Što je uopće pojam algoritam?
Pojam algoritam označava postupak ili niz precizno definiranih koraka koji se koriste za rješavanje nekog problema ili izvršavanje zadatka. Drugim riječima, algoritam je uputa korak po korak koja nam govori kako postići neki cilj.

Algoritmi sortiranja

Sortiranje je postupak organizacije podataka prema određenim pravilima, bilo to od najmanjeg do najvećeg broja, abecednim redom ili prema nekom drugom pravilu.. U informatici često sortiranjem činimo podatke preglednijima i lakšima za obradu.

Mjehuričasto sortiranje (Bubble Sort)

Način sortiranja elemenata kojim se najveći element gura na kraj liste naziva se mjehuričasto sortiranje (engl. Bubble sort).

Zamislite popis brojeva ili učenika kojeg trebamo posložiti od najmanjeg do najvećeg. Kako to radimo? Jedan od najjednostavnijih algoritama za sortiranje je mjehuričasto sortiranje. Algoritam se temelji na usporedbi dva susjedna elementa. Ako su u pogrešnom redoslijedu, zamijenimo ih, a postupak ponavljamo sve dok cijela lista ne bude pravilno posložena.

Koraci mjehuričastog sortiranja:

    1. Usporedi dva susjedna elementa.

    1. Ako je prvi element veći od drugog, zamijeni ih.

    1. Ponovi postupak za sve elemente dok najveći „ne ispliva“ na kraj liste.

    1. Postupak ponavljaj dok cijela lista ne bude sortirana.

Primjer: Lista: [5, 2, 4, 3, 1]

    1. korak: Usporedi 5 i 2 → Zamijeni → Lista: [2, 5, 4, 3, 1]

    1. korak: Usporedi 5 i 4 → Zamijeni → Lista: [2, 4, 5, 3, 1]
      … Sve dok lista ne postane: [1, 2, 3, 4, 5].

Primjena u Pythonu

Algoritam mjehuričastog sortiranja sastoji se od dviju petlji, unutarnje i vanjske. Unutarnja petlja nam služi za uspoređivanje susjednih elemenata niza te za njihovu zamjenu kada je to potrebno. Vanjskom se petljom osigurava ponavljanje uspoređivanja sve dok se svaki element ne dovede na odgovarajuće mjesto s obzirom na kriterij sortiranja.

Kod algoritma:

def sortiraj(lista):
    for i in range(len(lista)-1):
        for j in range(len(lista)-1-i):
            if lista[j] > lista[j+1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]
    print(lista)

Primjer:

a = [5, 2, 4, 3, 1]
sortiraj(a) Ispis: [1, 2, 3, 4, 5]

Objašnjenje algoritma red po red:

def sortiraj(lista):
Definicija funkcije: Ovo je početak funkcije sortiraj koja prima jedan argument lista. Ova lista je niz podataka (brojeva ili slova) koji će se sortirati koristeći algoritam mjehuričastog sortiranja.

for i in range(len(lista)-1):
Vanjska petlja: Ova petlja kontrolira broj prolaza kroz cijelu listu. Petlja se ponavlja len(lista)-1 puta, jer je maksimalno toliko prolaza potrebno da lista bude potpuno sortirana.
Zašto len(lista)-1? Svaki prolaz postavlja najveći element na pravo mjesto, pa se zadnji prolaz ne mora ponavljati za već sortirane elemente.

for j in range(len(lista)-1-i):
Unutarnja petlja: Ovo je “srce” algoritma. Ova petlja prolazi kroz sve susjedne parove elemenata u listi koji još nisu sortirani.
Duljina unutarnje petlje se smanjuje s brojem prolaza vanjske petlje (len(lista)-1-i), jer je svaki prolaz vanjske petlje već postavio najveći element na pravo mjesto na kraju liste, pa se taj dio više ne mora pregledavati.

if lista[j] > lista[j+1]:
Uvjet zamjene: Ovdje se provjerava jesu li dva susjedna elementa u pogrešnom redoslijedu (je li trenutni element veći od sljedećeg). Ako jesu, trebamo ih zamijeniti.

lista[j], lista[j+1] = lista[j+1], lista[j]
Zamjena elemenata: Ako su elementi u pogrešnom redoslijedu, zamijenimo njihove vrijednosti. Na primjer, ako je lista[j] = 5 i lista[j+1] = 3, nakon ove linije lista[j] će biti 3, a lista[j+1] će biti 5.

print(lista)
Ispis liste: Na kraju funkcije, ispisuje se konačno sortirana lista.

Što je unutarnja, a što vanjska petlja?

  1. Vanjska petlja (for i in range(len(lista)-1)):
    • Ova petlja osigurava da se cijela lista prolazi onoliko puta koliko je potrebno da se svi elementi sortiraju.
    • Na kraju svakog prolaza ove petlje, najveći element u nesortiranom dijelu liste bit će postavljen na odgovarajuće mjesto na kraju liste.
    • Broj ponavljanja se smanjuje jer se zadnji element svakim prolazom već sortira.
  2. Unutarnja petlja (for j in range(len(lista)-1-i)):
    • Ovo je petlja koja uspoređuje i zamjenjuje susjedne elemente.
    • Ponavlja se samo za nesortirani dio liste, jer se sortirani dio na kraju više ne pregledava.
    • Ova petlja radi “fino sortiranje” unutar jednog prolaza vanjske petlje.

Primjer rada:

Za listu [5, 2, 4, 3, 1], evo kako petlje rade:

  1. Prvi prolaz vanjske petlje (i=0):
    • Unutarnja petlja uspoređuje i zamjenjuje elemente:
      • Uspoređuje 5 i 2 → zamjena → [2, 5, 4, 3, 1]
      • Uspoređuje 5 i 4 → zamjena → [2, 4, 5, 3, 1]
      • Uspoređuje 5 i 3 → zamjena → [2, 4, 3, 5, 1]
      • Uspoređuje 5 i 1 → zamjena → [2, 4, 3, 1, 5]
    • Najveći element (5) “isplivava” na kraj liste.
  2. Drugi prolaz vanjske petlje (i=1):
    • Unutarnja petlja prolazi kroz prve 4 pozicije (bez zadnje):
      • Uspoređuje 2 i 4 → nema zamjene.
      • Uspoređuje 4 i 3 → zamjena → [2, 3, 4, 1, 5]
      • Uspoređuje 4 i 1 → zamjena → [2, 3, 1, 4, 5]
    • Drugi najveći element (4) “isplivava” na predzadnju poziciju.

I tako dalje, dok lista ne bude potpuno sortirana.

Sortiranje u stvarnom svijetu

Pitate se gdje ćemo to primijeniti? Zamislite sportsku tablicu koju trebate posložiti prema rezultatima natjecanja. Ili listu učenika prema broju osvojenih bodova na natjecanju. Ovi problemi nisu ništa drugo nego primjena algoritama sortiranja!

Razlika između sort() i sorted()

U sedmom smo razredu upoznali osnovne funkcije i metode za rad s listama, metodu sort() kojom možemo sortirati zadanu listu. U programskom jeziku Pythonu katkad se za sortiranje koristi i funkcija sorted(). U čemu je razlika?

Funkcija sorted() ispisuje sortiranu listu, ali ju ne mijenja, a metoda sort() zaista sortira zadanu listu nakon poziva funkcije, dakle mijenja izgled same liste.

Sortiranje velikih skupova podataka

Iako je mjehuričasto sortiranje jednostavno i odlično za male skupove podataka, kod velikih skupova koristimo naprednije algoritme, poput brzog sortiranja (Quick Sort) i spajajućeg sortiranja (Merge Sort). Ove metode omogućuju rješenja problema s velikim količinama podataka, kao što su analize podataka na društvenim mrežama ili organizacija velikih baza podataka.

  • Brzo sortiranje (Quick Sort) – podjela liste na manje dijelove.
  • Spajajuće sortiranje (Merge Sort) – spajanje sortirane pod-liste u cjelinu. Ovi algoritmi omogućuju brzo sortiranje velikih količina podataka, što je ključno u obradi baza podataka i analizi informacija.

Sortiranje znakova – Rad s tekstualnim vrijednostima u Pythonu

Kako sortirati znakove prema vrijednosti?

U računalima, svi znakovi (slova, brojevi, simboli) pohranjuju se u brojevnom obliku, koristeći kodni sustav poput Unicodea. Python nudi funkcije koje omogućuju rad s takvim kodnim vrijednostima:

  • ord(): Pretvara znak u njegovu brojnu vrijednost (npr. ord('a') vraća 97).
  • chr(): Pretvara brojnu vrijednost natrag u znak (npr. chr(97) vraća 'a').

Problem s velikim i malim slovima

Znakovi su u Unicode sustavu organizirani prema kodovima. Kod velikih slova (A-Z) manji je od kodova malih slova (a-z). To može dovesti do pogrešnog sortiranja kada kombiniramo velika i mala slova.

Primjer:

b = ['c', 'a', 'F', 'd', 'B', 'e']
b.sort()
print(b)
# Rezultat: ['B', 'F', 'a', 'c', 'd', 'e']  (velika slova sortirana prije malih)

Kako riješiti problem? Koristimo key=str.lower kako bismo sve znakove tretirali kao mala slova tijekom sortiranja.

Primjer s rješenjem:

b = ['c', 'a', 'F', 'd', 'B', 'e']
b.sort(key=str.lower)
print(b)
# Rezultat: ['a', 'B', 'c', 'd', 'e', 'F']

Vježbe

Vježba 1: Sortiranje znakova

Napišite Python program koji sortira niz znakova (mala i velika slova) koristeći sorted() ili sort() s ključem key=str.lower

  • Primjer unosa i izlaza:
    b = ['c', 'a', 'F', 'd', 'B', 'e']
    b.sort(key=str.lower)
    print(b)

Vježba 2: Sortiranje slova u imenu

Napišite program koji od korisnika traži unos imena, razdvaja ga na slova i sortira ih abecednim redom.

Primjer programa:

ime = input("Upiši ime: ")
ime = list(ime)
ime.sort(key=str.lower)
print(ime)

Primjer rezultata: Unos: Marko
Izlaz: ['a', 'k', 'm', 'o', 'r']

Vježba 3: Sortiranje popisa imena

Ako imate više imena odvojenih razmakom, možete ih unijeti kao niz i sortirati abecednim redom.

Primjer programa:

imena = input(“Upiši imena: “).split()
imena.sort()
print(imena)

Primjer rezultata: Unos: Leo Ana Maja Ante
Izlaz: ['Ana', 'Ante', 'Leo', 'Maja']

Kada ne možemo koristiti metodu sort()?

Kada god je moguće, dobro je za sortiranje podataka koristiti se ugrađenom metodom sort() jer to smanjuje broj programskih naredbi. No, postoje situacije kada moramo primijeniti neki algoritam sortiranja umjesto ugrađene metode sort(). 

Projektni zadatak

Grupni rad

Podijelite se u grupe i osmislite računalni program koji može automatski složiti raspored učenika prema rezultatima testa, s opcijom prikaza najboljeg i najlošijeg rezultata.

PROVJERI SVOJE ZNANJE

  1. Što je mjehuričasto sortiranje?
  2. Objasnite kako radi mjehuričasto sortiranje.
  3. Napišite Python kod za sortiranje brojeva od najvećeg prema najmanjem.
  4. Kako razlikujemo sort() i sorted() u Pythonu?
  5. Koje napredne metode sortiranja poznajete?