FONForum

Imas na slajdu o sortiranju koji mozes da skines sa sajta struktura. Ako me ne bude mrzelo okacicu kasnije.

edit:
Evo i objasnjenja za pitanja iz raznih tema:

Povezana lista
Povezana lista (linked list) je nista drugo nego niz elemenata, od kojih svaki ima 2 polja. U jednom je vrednost elementa (ono sto bi bilo na tom mestu u obicnom nizu), a u drugom pokazivac na sledeci element niza. Zadnji element pokazuje na NULL.

Prednosti ovakve strukture podataka su ubacivanje i izbacivanje elemenata iz liste u vremenskoj slozenosti O(1).

Stek
Stek (stack) je LIFO (Last In First Out) lista. Naime, kada treba smestiti novi element u stek, on se stavlja na njegov kraj (PUSH operacija), pri cemu se i pri uzimanju elemenata sa steka oni takodje uzimaju sa kraja (POP operacija). Stek inace koristi i sam kompajler pri rekurziji, tako da je jedna od primena steka bas simuliranje rekurzije.

Red
Red (queue) je FIFO (First In First Out) lista. U ovu listu se elementi stavljaju na kraj, ali uzimaju sa pocetka (kao red u prodavnici).

Hash tablice
Hash tablice (hash tables) nastaju hashiranjem elemenata. Naime, svaki element koji zelimo smestiti u ovu strukturu podataka hashiramo, tj. sracunamo vrednost koju neka hash funkcija daje za njega, i smestimo na to mesto u tabelu. Primer: Treba zapamtiti imena ucenika nekog razreda i jos neki podatak o svakom, recimo broj telefona. Primer hash funkcije je recimo zbir ascii vrednosti svih slova u imenu po modulu velicine tablice (sto je najpozeljnije neki prost broj). Ako je to mesto vec zauzeto, dodajemo jos jedan unos u isto polje (mozemo hash tablicu dakle pamtiti kao matricu, ili kao niz povezanih listi, sto je bolja implementacija). Sada kad trebamo naci Markov broj telefona, sabracemo ascii vrednosti slova u reci "Marko", uzeti tu vrednost po modulu velicine tablice, i traziti na tom mestu u hash tablici. Prednost ove strukture podataka je vreme pristupa elementu O(1).

Drvo
Za one koji su upoznati, drvo (tree) predstavlja graf koji nema nijedan krug (ciklus). Koncepcija ove strukture podataka je vec i iz samog imena jasna, a narocito uz sliku:

Za neki pocetni cvor kazemo da je "koren" (root) drveta, za svaki cvor one koji su "nadole" od njega i direktno povezani sa njim kazemo da su njegova "deca" (children), a zajedno sa onima nadole sa kojima je povezan preko vise od jedne ivice kazemo da su njegovi "potomci" (descendants). Svaki cvor koji je "nagore" od nekog i povezan sa njim je njegov "predak" (ancestor). Neki cvor zajedno sa svim njegovim potomcima cini poddrvo (subtree) ciji je on root. Najcesce se koristi binarno drvece, u kome svaki cvor ima najvise dvoje dece. Takodje, ovde svaki cvor ima svoje levo i desno poddrvo.

Binarno drvo pretrage
Binarno drvo pretrage (binary search tree) je takvo drvo u kome je za neki cvor njegovo levo dete uvek manje od njega, a desno uvek vece. U ovakvom drvetu je za trazenje ubacivanje ili izbacivane nekog elementa potrebno vreme O(log n). Medjutim, ako su elementi lose rasporedjeni, svaka od ovih operacija moze odneti cak O(n) vremena!

AVL drvo
AVL drvo je "izbalansirano" binarno drvo pretrage. U njemu je razlika visina levog i desnog poddrveta za svaki cvor najvise 1. Naime, pri svakom dodavanju ili izbacivanju elemenata, obraca se paznja da drvo ostane izbalansirano kao sto je receno, pri cemu se za taj korak ne sme potrositi vise od O(log n) vremena. Slozenosti svih operacija su kod ovakvog drveta uvek tacno O(log n).

Heap
Heap je jos jedna vrsta binarnog drveta, kod koga je zadovoljen uslov da su deca svakog cvora uvek veca ili jednaka od samog tog cvora (moze se praviti i obrnuto, da su deca uvek veca od oca). Ova struktura podataka ima izuzetno sirok spektar upotrebe. Naime, cesto je potrebno u svakom trenutku znati koji je najmanji element nekog niza. Koristeci heap, ovu informaciju imamo u O(1) (to je ustvari prvi element u heap-u). Updateovanje heap-a, sto ce reci izbacivanje ili ubacivane elementa radi se u O(log n).

Trazenje u hash tablicama
Ako koristimo hash tablice, trazenje elementa je vrlo jednostavno. Samo ga treba "pluggovati" u hash funkciju i time ga nadjemo u O(1).

Trazenje u binarnom drvetu pretrage i AVL drvetu
I ove strukture podataka, kao i hash tablice, su takve da im je jedna od poenti upravo trazenje elemenata. Kod obe je proces isti: podjemo od root-a celog drveta. Ukoliko je on element koji trazimo, kraj. Ako ne, vidimo da li je element koji trazimo manji ili veci od njega. Ako je manji, isti postupak (rekurzivno) ponavljamo za levo poddrvo, ako je veci za desno. Kao sto je vec receno, slozenost je O(log n), sa tim da u nebalansiranom drvetu moze da bude i znatno gora (ali i bolja!).


Linearna pretraga
Pretpostavimo da imamo obican niz od n elemenata. Linearna pretraga se sastoji u tome da prodjemo sve elemente niza trazeci onaj koji nam treba. Slozenost: O(n).

Binarna pretraga
Imamo sortiran (rastuce) niz od n elemenata u kome treba naci neki. Neka je na pocetku left=1 i right=n. U svakoj iteraciji, nadjemo element middle kao srednji izmedju left i right. Ukoliko je trazeni element jednak tom middle, kraj. Ako je middle veci od njega, kazemo right=middle, u suprotnom left=middle, i ponavljamo isti postupak. Vrlo jednostavan, ali vrlo cesto upotrebljavan koncept. Slozenost je, naravno, O(log n).

Selection, Insertion i Bubble Sort
Ovo su tri vrlo jednostavna algoritma za sortiranje elemenata. Svi su izuzetno jednostavni, ali slozenosti O(n²).

Quick Sort
Verovatno najbolji algoritam za sortiranje. Radi po sledecem principu: odredimo neki, bilo koji, element da bude pivot. Sada ispremestamo sve elemente niza tako da su prvo svi oni manji, pa onda svi oni veci od pivota. Sada, za svaki od ova dva dela rekurzivno pozovemo quicksort. Izuzetno elegantan i praktican algoritam, a lak za kodiranje. Slozenosti je O(n log n), mada ona nije uvek ista. U najgorem mogucem slucaju ona moze biti i O(n²), medjutim, u praksi, quicksort obicno daje bolje rezultate od svih ostalih algoritama za sortiranje.

Merge Sort
Merge Sort radi na principu “podeli i vladaj”. On naime podeli niz na dva dela, rekurzivno se poziva za oba, a kada se vrati, ta dva dela spaja (merge) u jedan sortirani. Slozenost je uvek O(n log n). Merge sort se jos moze i koristiti za racunanje broja inverzija permutacije, uz par redova dodatih u trenutku kada se nizovi spajaju.

Heap Sort
Heap Sort niz sortira tako sto ga smesti u heap. Vec znamo da operacije umetanja i skidanja sa heapa imaju slozenost O(log n). Dakle ovaj algoritam ce imati ukupnu slozenost O(n log n), jer svaki element treba prvo da ubacimo u heap, pa kad smo formirali ceo, izbacujemo uvek prvi element dokle god ne ispraznimo heap.


preuzeto sa ES

ili:
Selection sort:

kompleksnost O(n²),
efikasnost O(n²/4),
najbrzi medju O(n²)

Shell sort:

kompleksnost O(n²),
efikasnost O(n log² n),
najefikasniji medju O(n²)

Insertion sort:

kompleksnost O(n²)
efikasan pri malom broju elemenata

Bubble sort:

kompleksnost O(n²),
efikasnost O(n*(n-1)),
najgori medju O(n²)

Quick sort:

kompleksnost u proseku O(n log n), u najgorem slucaju O(n²)
cesto najbrzi

Merge sort:

kompleksnost O(n log n),
malo brzi od Heap-a pri velikom broju elemenata

Heap sort:

kompleksnost O(n log n)
najsporiji medju O(n log n)

Kako ide struktura zadataka na II kol?
- crtanje 2x (avl + B*) ?
- kodovi 2x (rekurzija) ?
- teorija - šta od iste, neka skripta ?

ILI

- crtanje 1x (avl ili B*) ?
- kodovi 3x (rekurzija) ?
- teorija - šta od iste, neka skripta ?