Alogoritmi

Nemanja666

Nemanja666

Obećava
Poruka
99
I ja sam mislio kao sto su neki i predlozili najbolje bi bilo da otvorimo posebnu temu za ovako veliku oblast.

Kroz citavu ovu temu u sledeci nekoliko sedmica pokusacu da objasnim stovise alogoritama koji su potrebni kod izrade programa. Alogoritmi ce biti iz oblasti: sortiranja, binarnog pretrazivanja, GRAFOVI, rad sa stringovima, rad sa matricama, rad sa velikim brojevima itd...

Pa da pocnemo!
 
Samo da prebacim iz one teme sta smo vec napisali:

Prvo cu da pojasnim alogoritme za sortiranje.

Cesto u programiranju javlja potreba da se neki podaci sortiraju u neopadajucem ili u nerastujecem redu. Postoji mnogo alogoritama koji sluze za ovu zadacu a neki su:
Bubble sort, Merge sort, Radix sort, Quick sort ...

Danas cu da objesnim najjednostavniji naravno i najsporiji Bubble sort(metodu mjehurica). Procedura za ovaj alogoritam izgleda ovako:

Kod: 
type
  TNiz = array[1..1000] of integer;

procedure Bubble_Sort(Count : integer; var niz : TNiz);
var
  i, j : integer;
begin
  for i := Count - 1 downto 1 do
    for j := 1 to i do
      if niz[j] > niz[j + 1] then
        begin
          Temp := Niz[j];
          Niz[j] := Niz[j + 1];
          Niz[j + 1] := Temp; 
        end;
end;

To bi bilo to. Alogoritam koristi dvije for petlje(vanjska i unutrasnja) u principu program provjerava dva uzastopna clana niza i rotira ih ako je prvi veci od drugog. Ovim se postiza da se svakim ciklusom unutrasnje petlje najveci broj u nesortiranom djelu niza postavi na krajnje mjesto u nesortiranom djelu niza cime zadnji clan postaje sortiran.

@bojan_p:

Samo mala dopuna na temu algoritama za sortiranje.

Generalno algoritmi za sortiranje se mogu podeliti u dve grupe u zavisnoti od brzine njihovog izvršavanja - odnosno kompleksnosti. U prvu grupu algoritama za sortiranje kojima je vreme izvršavanja proporcionalno n*n, gde je n broj elemenata koji se sortiraju spadaju: Bubble sort, Selection sort, Insertion sort i Shell sort. U drugu grupu gde je vreme izvršavanja proporcionalno n * log n spadaju: Heap sort, Merge sort i Qucik sort.

Iako više algoritama pripada istoj grupi brzina njihovog izvršavanja se razlikuje. U prvoj grupi algoritma najbrži je: Shell, a potom slede Insertion, Selection i na kraju Bubble sort.
 
Prvo da vam pokazem kako da ubjedljivo sortirate niz. Ovaj nije alogoritam ali je dobar nacin za extra brzo sortiranje niza. recimo da trebamo da sortiramo nekoliko milijuna brojeva u rasponu od 0 do 999999. Onda je najbrza ovako:
Kod: 
type
  TNiz = array[1..999999] of integer;

procedure ArraySort(InArray : TNiz; OutArray : TNiz; n : longint);
var
  i : longint;
begin
  for i := 1 to n do
    Inc(OutArray[InArray[i]])
end;
sad da napisemo proceduru za ispis
Kod: 
procedure ispisi(Sender : TNiz);
var
  i : longint;
begin
  for i := 1 to 999999 do//maksimalan index od niza
    for j := 1 to Sender[i] do writeln(i);
end;
Veoma jednostavno veoma brzo. Prica ide ovako:
Imamo nesortiran niz. Jednom for petljom ga prelazimo samo JEDNOM i za svaku vrijednost polja u nizu povecavamo vrijednost polja u drugom nizu kome odgovara index vrijednosti polja u prvom nizu. Sa procedurom Ispisi ispisujemo sortiran niz na desktop prolazimo drugi(sortirani) niz od pocetka do kraja i gdje vrijednost polja 1 jednom ipisujemo index od toga polja, gdje je vrijednost polja 2 ispisujemo index toga polja DVAPUT i tako dalje.

Pozdrav! Sutra Merge sort!
 
Prethodno izneti algoritam ima neka ograničenja:

  • veličina OutArray niza mora bit jednaka opseg brojeva koji se sortiraju;
  • mogu se sortirati samo celi brojevi (Integer);
  • za velike opseg zahteva dosta memorije, tako da iako nije vremenski zahteva prostorno jeste;
  • obično se niz sortira da bi se rezultat upotrebio za dalju obradu, pa je potrebno napraviti niz koji predstavlja rezultat sortiranja, a ne samo ga ispisati (ovo nije problem uradit i za to se može iskoristiti ulazni, nesortirani niz).
 
Imas pravo bojane za sve nedostatke, ali ponekad(veoma rijetko) zadatak ispunjava ove uslove, a potrebna je velika brzina.

Quick sort

Quick sort ili brzo sortiranje je jedan od najbrzi alogoritama za sortiranje i meni omiljeni. Zasniva se na ideji podeli pa vladaj. Imamo ulazni nesortirani niz od koga uzimamo jedan proizvoljan element(obicno pocetni, srednji ili zadnji ja uvek uzimam srednji) i zatim uredjujemo niz tako da svi elementi manji od uzetog elementa budu lijevo, a svi veci ili jednaki da budu desno. Nakon ovoga uzeti element se nalazi na odgovarajucem mjestu nakon ceka se funkcija poziva rekurzivno za levi i desni dio niza.

Brzina ovog alogoritma je n * log(n).

Alogoritam zapisujemo funkcijom:

Kod: 
procedure quicksort(var Niz : TNiz; Lo, Hi : integer);

procedure sort(left, right : integer);
var
  i, j, x, Temp : integer;
begin
  i := left; j := right; x := Niz[(left + right) div 2];
  repeat
    while Niz[i] < x do Inc(i);
    while Niz[j] > x do Dec(j);
    if i <= j then
    begin
      Temp := Niz[i]; Niz[i] := Niz[j]; Niz[j] := Temp;
      Inc(i); Dec(j);
    end;
  until i > j;
  if left < j then sort(left, j);
  if i < right then sort(i, right);
end;

begin {quicksort};
  sort(Lo, Hi);
end;

To bi Quick saort a sada

Merge sort

Osnovna ideja ovog sorta je da od dva sortirana niza napravimo treci kao rezultat spajanja ta dva niza. Merge sort je dobar za senkvencijalno sortiranje, ali za sortiranje jednog niza nije populara, jer se prvo mora niz razbiti na dva niza pa da se nizovi sortiraju nekim drugim alogoritmom(obicno Quick sortom) pa da se zove funkcija za spajanje ova dva niza. Ja cu sad objasniti samo funkciju za spajanje dva niza.

Napisace mo je veoma jednostavno. Postavicemo jednu repeat..until petlju sa kojem ce mo prebacivati elemente u zavrsni niz i trebaju nam dvije varijable kojim cemo da pretrazivati prva dva SORTIRANA niza.

Kod: 
procedure Merge(a, b : TNiz; a_size, b_size : integer; var Result : TNiz);
var
  i, j, k, x : integer;
begin
  k := 1; i := 1; j := 1;
  repeat
    if a[i] < b[j] then
      begin
        Result[k] := a[i];
        Inc(i);
      end
    else
      begin
        Result[k] := b[j];
        Inc(j);
      end;  
    Inc(k);
    if (i > a_Size) or (j > b_size) then break;
  until k = (a_size + b_size) + 1;
  for x := i to a_size do
    begin
      Result[k] := a[x];
      Inc(k); 
    end;
  for x := j to b_size do
    begin
      Result[k] := b[x];
      Inc(k);
    end;
end;

Kao sta se vidi u kodu u rezultujuci iz sortiramo elemente u neoopadajuci poredak sve dok sve dok jednog niza neponestane a zatim iz preostalog niza prepisemo elemente u u rezultujuci niz.

Napomena: Dva ulazna niza moraju biti sortirana u neopadajucem redosledu.

Mislim da oko sortiranja nema punu da se pise. Bitno je znati barem jedan alogoritam. Obicno on bude dovoljan. Mislio sam da napisem objasnjenja za jos pokiji alogoritam za sortiranja ali mislim da nema potrebe. Imate Buble sort koji je veoma jednostavan, Quick sort koji je veoma brz i znamo spojiti dva sortirana niza u jedan sortiran. Ako jos neko nesto zeli o sortiranju neko napise, a sledeci put binarno pretrazivanje. Oko pretrazivanja se necemo puno zadrzavati uradicemo Binarno drvo i Crveno-Crno drvo.
 
Prije neko sto pocnemo se baviti oko sekvencijalnog pretrazivanje prvo cemo se podsjetiti kako se u pascal-u koriste pokazivaci.

Pokazivaci

Pokazivace nisu tipovi jer oni nesadrze nikakve vrijednosti neko samo pokazuju na adresu u memoriju gdje se podaci sacuvani. Njih deklarisemo kao i ostale tipove uz razliku da pred ime tipa stavljamo znak ^ koji daje doznanja da se o tipu neko na pokazivac koji pokazujena taj tip.

Razlika kod deklarisanja tipa i pokazivaca:

Kod: 
var
  var1 : integer; //podatak tipa integer-a
  pok1 : ^integer; //pokazivac na tip integer-a

Pozivanjem procedure new kreirase nova dinamicka varijabla.

Kod: 
program primjer2;
var
  pok : ^integer;
begin
  new(pok);
  pok^ := 5;
  writeln(pok);
end.

Izvrsavanjem prograva gore prvo stvaramo promjenjivu pok. Nakon pozivanjem procedure new(pok) obezbjedjuje se memoriski prostor za promjenjivu pok^ i pokazivacu pok dodeljuje se memoriska adresa za novo nastalu varijablu. Druga linija koda obezbedjuje da se memoriskoj lokaciji na koju pokazuje dodjeli vrijednost 5, i treca linije reda ispusuje vrijednost memoriske lokacije.
Napocetku programa pokazivaci nepokazuju ni na jednu lokaciju. Sem pozivanjem procedure new pokazivacu mozemo dodjeliti memorisku lakaciju nekog drugog pokazivaca.

Kod: 
program primjer3;
var
  pok1, pok2 : ^integer;
begin
  new(pok1);
  pok1^ := 1;
  new(pok2);
  pok2^ := 2;
  pok1^ := pok2^;
  pok2 := pok1;
  pok1 := nil;
end.

Promjer gore nema nikakvog smisla samo sam ga napisao da vam objasnim operacije nad pokazivacima. Prve cetiri linije koda znamo sta rade. Peta linija koda kopira vrijednost memoriske lokacije na koju pokazuje pokazivac pok2 u memorisku lokaciju na koju pokazuje pokazivac pok1. Sledeca linije nedira memoriske lokacije nego pokazivac pok2 ukazuje na lokaciju na koju pokazuje pok1, Ova je sad los kod jer je memoriska lokacije na koju je pokazivao pokazivac pok2 postala nedostupna za program, a jos se uvijek nalazi u memoriji. Pokazivacima mozemo dodjeliti i vrijednost nil. Nil nije isto kao kad pokazivac nepokazuje nigdje, jer dok pokazuje na nil mozemo ga porediti. Pokazivace mozemo porediti samo sa jednako ili nije jednako(=, <>). Nemojte se zabuniti jer vrijednosti memoriske adresa na koju pokazivac pokazuje mozemo porediti kao sve tipove. I samo nakraju da kazem da se memoriska lokacija moze unistiti sa procedurom dispose(_ime_pokazivaca_). Unistava se momoriska lokacija na koju pokazuje trenutno pokazivac. Poslije ove procedure pokazivac nepokazuje ni na jednu memorisku lokaciju ili nil.
 
Binarno drvo

Kada radimo sa pretrazivanjem podataka svakako zelimo da izbjegnemo poredjenem sa svakim clanom kolekcije podataka. Zbog toga je uveden pojam drveta. Prvo cu vam objasniti binarno drvo. Drvo je skup korijena(cvorova) i njegovih naslednjika. Drvo je binarno je ako kod svakom korijenu priduzene neka vrijednost iz kolekcije podataka i ako je od svakog korijena vrijednosti manje ili jednake od vrijednosti tog korijenja nalaze lijevo, a vece vrijednosti nalaze se desno.

binary-tree-add.gif


Strukturu koju cemo koristiti za prokazivanje cvorova kod binarnog drveta mozemo napisati na sledeci nacin:

Kod: 
type
  Pokazivac = ^TBinCvor;
  TBinCvor = record
    Value : integer;
    ldr : Pokazivac;
    rdr : Pokazivac;
  end;
;

Value drzi jednu vrijednost iz kolekcije podataka. Ldr je pokazivac na drvo lijevo, a rdr pokazivac na drvo desno. Sada ce mo napisati program za umetanje u binarno drvo.

Kod: 
program binarno_drvo;
type
  Pokazivac = ^TBinCvor;
  TBinCvor = record
    Value : integer;
    ldr : Pokazivac;
    rdr : Pokazivac;
  end;
var
  pocetni_cvor : Pokazivac;
  InValue : integer;
  InStr : string;
procedure NoviCvor(Sender : integer);
var
  Cvor, Pred_Cvor : Pokazivac; 
begin
  Cvor := pocetni_cvor;
  if Cvor = nil then
    begin
      New(Cvor);
      Cvor^.Value := Sender;
      Cvor^.ldr := nil;
      Cvor^.rdr := nil;
      pocetni_cvor := Cvor;
      exit;
    end;
  repeat
    Pred_Cvor := Cvor;
    if Sender <= Cvor^.Value then
      Cvor := Cvor^.ldr
    else
      Cvor := Cvor^.rdr;
  until Cvor = Nil;
  New(Cvor);
  Cvor^.Value := Sender;
  Cvor^.ldr := nil;
  Cvor^.rdr := nil;
  if Sender <= Pred_Cvor^.Value then
    Pred_Cvor^.ldr := Cvor
  else
    Pred_Cvor^.rdr := Cvor;
end;

begin
  pocetni_cvor := nil;
  repeat
    writeln('Unesite vrijednost:');
    readln(InValue);
    NoviCvor(InValue);
    writeln('Da li zelite umetnuti jos jedan cvor?(D/N):');
    readln(InStr); 
  until InStr = 'N';
end.

U primjeru imamo jedan globalni pokazivac <pocetni_cvor> koji pokazuje pocetni cvor(korijen drveta). Ovoj pokazivac nam je vazan da bi znali gdje se citavo drvo nalazi u memoriji. Program neradi nista posebno sta bi mogli vidjeti, mi samo mozemo unositi podatke. U narednim tutorijalima ce mo uraditi trazenje po drvetu i brisanje vrijedmosti iz drveta, a sad da se vratimo u alogoritam za upis u drvo. Ako je pocetni cvor ima adresu nil onda znamo da drvo nepostoji i jedino sto trebamo stvoriti jedan cvor i proglasiti ga pocetnim tako sto poklazivacu <pocetni_slog> dodjeljujemo njegovu adresu. ako postiji onda se krecemo po drvetu po njegovom svojstvu(ako je broj koji je trebamo ubaciti manji ili jednak od vrijednosti u cvoru u kome se nalazimu idemo ulijevo suprotno idemo udesno). Kada dodjemo do pokazivaca koji pokazuje na nil to znaci da nasu vrijednost treba staviti na to mjesto. Posto nam pokazivac <Cvor> pokazuje na nil zato smo uveli pokazivac <Pred_cvor> koji pokazuje na adresu prije nego sto pokazuje pokazivac <Cvor>. Nakon toga cuvamo novi cvor podesavamo njegovu vrijednost, a cvor koji mu predhodi povezujemo sa njim.
 
Sutra ce biti nastavak tutoriala o binarnom drvetu, nisam imao vremena zbog skole. Poslije ovog tutoriala mislio sam da uradimo i crveno-crno drvo ali ako zelite da odmah predjemo na grafove i dinamicko programiranje pisite.
 
Binarno drvo - pretrazivanje

Najvaznija operacija kod binarnog drva je pretrazivanje. Oko pretrazivanje nema puno price. Pocinjemo da usporedjujemo vrijednosti koje su dodjeljene cvorovima i to od korijena drveta, i pratimo svojostva drveta(lijevo su manje ili jednake vrijednosti, a desno su vece vrijednosti). Sada cemo napisati funkciju za pretrazivanje koja ce raditi kada se umetne u program iz predhodnog tutorijala. Funkcija prima vrijednost koju je potrebno pronaci u drvetu i pokazivac na cvor od kojega pretrazivanje pocinje,a vraca na pokazivac na cvor kod kojega se PRVOG javlja trazena vrijednost.

Kod: 
function Pretrazi(Sender : integer; Root : pokazivac) : pokazivac;
begin
  result := Root;
  while (result^.Value <> Sender) or (result <> nil) do
    if result^.Value < Sender then result := result^.rdr
    else result := result^.ldr;
end;

Ovo je citava funkcija za pretrazivanje binarnog drveta. Jednostavna je, zar ne? Evo kako na radi:
Kao izlaz postavljamo cvor koji je prosljedjen funkciji kao pocetni. Koristimo while do umjesto repeat until petlje jer nam je potreban izlaz iz petlje ako joj kao pocetni cvor proslijedimo nil. if petljom postizemo da se krecemo kroz drvo lijevo desno. Kad je broj pronadjen result funkcije je pokazivac na trazeni cvor ili ako nije pronadjen ima vrijednost nil.
 
Nemanja666:
Binarno drvo

Kada radimo sa pretrazivanjem podataka svakako zelimo da izbjegnemo poredjenem sa svakim clanom kolekcije podataka. Zbog toga je uveden pojam drveta. Prvo cu vam objasniti binarno drvo. Drvo je skup korijena(cvorova) i njegovih naslednjika. Drvo je binarno je ako kod svakom korijenu priduzene neka vrijednost iz kolekcije podataka i ako je od svakog korijena vrijednosti manje ili jednake od vrijednosti tog korijenja nalaze lijevo, a vece vrijednosti nalaze se desno.

[slika1] ???

Strukturu koju cemo koristiti za prokazivanje cvorova kod binarnog drveta mozemo napisati na sledeci nacin:

Kod: 
type
  Pokazivac = ^TBinCvor;
  TBinCvor = record
    Value : integer;
    ldr : Pokazivac;
    rdr : Pokazivac;
  end;
;
Kliknite za proširenje...
Jel' to koristis copy/paste sistem iz nekog prirucnika ?
Daj bar prekopiraj i slike ako ih ima...

Zanimljivo i hvale vredno sakupljanje cinjenica da ljudi lakse nauce (cak sam i glasao pozitivno za temu), ali bar navedi izvore prirucnika iz kog si radio copy/paste svih ovih kodova, pa onaj ko zeli moze sam da prosiri znanje citajuci. Ovako ispada da ti to "iz glave" pises tutorijale a to bas i nije fer ponasanje.
 
Izvor moja glava. Naucio sam davno sta nekim knjigama najvise iz knjige Alogoritmi u programskom jeziku C, Dosta vjezbe i jedan iskusniji prijatelj koji mi je pomagao. Pisao sam taj tutorijal pa sam ga kasnije stavio na forum. Tu sam trebao staviti sliku cvora, ali sam zaboravio. Sad ima.

Slika je sa Google-a.
 
Samo nastavi, Nemanja! (Ne zaboravi na balansiranje binarnog stabla ;) )

Ako vec nemas, nabavi knjigu Strukture podataka, prirucnik za istoimeni predmet na ETF-u, tamo ima jos vise.
 
Prvo ide pravljenje, pa pretraživanje, a tek onda balansiranje... ;)

Najčešće i bude "iz glave", a sigurno da za svaku od ovih tema-postova može da se navede bar par izvora. Samo nastavi Nemanja.
 
Ovako oko binarnog drveta ostalo nam je da uradimo proceduru za brisaje cvorova koja je malo teza od ostalih, a poslije toga pokusacemo da vrsimo balansiranje drveta jednim nacinom koji se zove rotacije. Uskoro.
 
Postoje dve vrste složenosti algoritma vremenska i prostorna (memorijska). Složenost algoritma predstavlja odnos između broja podataka koje algoritam obrađuje i vremena njegovog izvršavanja odnosno prostora koji je potreban. Većinom se pod složenošću podrazumeva vremensa složenost. Složenost se izražava Big-Oh notacijom. Najčešće složenosti algoritama su: O(n), O(n log n) i O (n*n).
 
U bilo kom algoritmu O(n) znači da je složenost algoritma linearna, kao što O(n*n) znači da je složenost kvadratna. Ako dva algoritma imaju složenost O(n) to i dalje ne znači da rade istom brzinom, odnosno zauzimaju isti prostor ako je reč o prostornoj složenosti, jer se pri određivanju složenosti ignorišu konstante pa je 4n=O(n), ali je i 1000n=O(n).
 
Prijavite se ili registrujte da biste poslali poruku.

Back
Top