Algoritmi sortiranja

Ishodi

OŠ INF B.8.1. identificira neki problem iz stvarnoga svijeta, stvara program za njegovo rješavanje, dokumentira rad programa i predstavlja djelovanje programa drugima
OŠ INF B.8.2. prepoznaje i opisuje algoritam sortiranja, primjenjuje jedan algoritam sortiranja za rješavanje zadanoga problema u programskom jeziku
uku A.3.1. Učenik samostalno traži nove informacije iz različitih izvora, transformira ih u novo znanje i uspješno primjenjuje pri rješavanju problema.
osr A.3.3. Razvija osobne potencijale.

Ciljevi učenja

  • Razumjeti kako algoritmi sortiranja funkcioniraju kroz praktične primjere.
  • Primijeniti algoritme sortiranja za rješavanje problema u svakodnevnom životu.
  • Pisati i testirati računalni program koji implementira algoritme sortiranja u Pythonu.
  • Razviti sposobnost samostalnog istraživanja i učenja novih koncepata.
  • Razvijati logičko razmišljanje i algoritamski način rješavanja problema.

UVOD

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.

GLAVNI DIO

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.
  2. Ako je prvi element veći od drugog, zamijeni ih.
  3. Ponovi postupak za sve elemente dok najveći „ne ispliva“ na kraj liste.
  4. 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]
  2. 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.

Zaključak

Danas smo naučili kako jednostavni algoritmi poput mjehuričastog sortiranja imaju ključnu ulogu u rješavanju problema iz stvarnog života. Sortiranje nije samo alat informatičara – to je logika koja nas okružuje, od organizacije podataka do svakodnevnog života.

ZAVRŠNI DIO

  • Provjerite svoje znanje. – KAHOOT KVIZ
  • dodatni digitalni sadržaji na e-Sfera
  • Provjerite svoje znanje.

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?