Pretraživanje i razvrstavanje polja

1. Pretraživanje polja

Najčešći tipovi podataka:

• int
• float
• char
• string
• bool

Vrste polja:

• jednodimenzionalna
• dvodimenzionalna

Pretraživanje polja:

• prema indeksu 
• prema vrijednosti

Metode pretraživanja polja:

• slijedno (linearno ili sekvencijalno) - brute - force
• binarno

2. Primjer pretraživanja polja slijednom (linearnom ili sekvencijalnom) metodom

1. primjer: Pretraživanje polja rezultata trčanja na 100 m. Tražimo najsporijeg učenika.

2. primjer: Pretraživanje polja rezultata trčanja na 100 m. Tražimo najbržega učenika, a učenika koji nije trčao i čiji je rezultat označen s 0 preskačemo.

3. primjer: Dodjeljivanje ocjena učenicima na temelju ljestvice ocjenjivanja

3. Slijedna (linearna ili sekvencijalna) metoda pretraživanja polja

Slijedno (linearno ili sekvencijalno) pretraživanje izvodimo prolaskom kroz cijelo polje tražeći element po nekom ključu, svaki puta uspoređujući dohvaćeni element polja sa traženom vrijednošću. 

Ova je metoda prikladna za nesortirana polja. 

Nedostatak joj je što je spora, pa se koristi rjeđe od metode binarnog pretraživanja.

4. Primjer pretraživanja polja binarnom metodom

1. primjer: Binarom metodom pretraživanja polja tražimo poziciju najsporijeg rezulatata

2. primjer: U polju podataka za skok u dalj pronaći poziciju podatka određene duljine skoka u cm

5. Binarna metoda pretraživanja polja

Metoda binarnog pretraživanja polja omogućuje da u svakoj iteraciji raspolovimo „prostor“ koji pretražujemo. 

Zbog toga je metoda efikasnija i češće se koristi od slijedne (linearne ili sekvencijalne). 

Koraci: 

1. postavimo granice niza=0 i visa=n-1 na temelju indeksa elemenata polja
2. zatim se izračuna sredina (radi se sa cijelim brojevima pa će rezultat dijeljenje biti odrezana cijela vrijednost):

sredina=(niza+visa)/2;

1. time je broj članova polja raspolovljen i provjerava se je li traženi podatak veći od podatka na polovici polja
2. ako jest promatranje počinje iza polovice tako da se za nižu granicu postavi: srednja+1
3. ako je pogođen traženi rezultat ispisuje se poruka o poziciji traženog podatka u polju:  srednja+1
4. ako je traženi podatak  manji od podatka na polovici polja, visa se granica postavlja na: srednja-1
5. ukoliko je niža granica veće vrijednosti od više ispisuje se poruka da se traženi podatak ne nalazi u polju

6. Metode razvrstavanja (sortiranja) polja

Neki od najkorištenijih algoritama za razvrstavanje polja: 

• Selection Sort
• Bubble Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Heap Sort
• Counting Sort
• Radix Sort
• Bucket Sort

7. Razvrstavanje odabirom- selection sort

*Video je sa stranice  Geeks for Geeks A computer science portal for geeks

Razvrstavanje odabirom (selection sort) je jedan od najjednostavnijih  algoritama za razvrstavanje elemenata polja.

Opis algoritma: 

1. nađi najmanji element polja, zamijeni ga s prvim elementom polja
2. nađi slijedeći najmanji element, zamijeni ga s drugim elementom polja
3. nađi treći najmanji element polja, zamijeni ga s trećim elementom polja
4. ponavljaj pronalaženje najmanjih elemenata i mijenjaj ih s elementom na odgovarajućoj poziciji dok god polje nije sortirano 

Programski kod:

Algoritam razvrstavanja odabirom (selection sort) je neefikasan za soritranje velikog broja podataka. 

8. Primjer algoritma za razvrstavanje polja metodom razmjene (selection sort)

Primjer zadatka:

Izradi simulaciju izvlačenja brojeva i formiranja Joker broja za igru Loto 6/45. 

1. deklarirati cjelobrojno polje od 6 brojeva
2. polje napuniti rand() funkcijom cijelim brojevima iz raspona 1 do 45
3.  provjeriti da se ne bi dogodilo da se brojevi slučajno ponove (ako se ponavljaju generirati novi broj)
4.  na temelju izvučenih brojeva izraditi Joker broj koji se formira od znamenki jedinica brojeva redoslijedom kojim su izvučeni, npr.

1. ispisati generirano polje
2. ispisati Joker broj
3. sortirati polje od najmanjeg prema najvećem metodom selection sort 
4. ispisati sortirano polje

9. Razvrstavanje polja metodom mjehurića (bubble sort)

Algoritam uzlaznog sortiranja funkcionira na slijedeći način:

10. Primjer algoritma za razvrstavanje polja metodom mjehurića