sortiranje/knjige/zad-sort2.txt

   1 ************************************************************
   2                 Zadatak za vežbu - sortiranje 2
   3 ************************************************************
   4
   5 Zadatak
   6 ============================================================
   7
   8 Zadatak sa prvih vezbi prosiriti sledecim funkcionalnostima:
   9
  10 metod za sortiranje
  11 -------------------
  12
  13 umesto da se koristi Arrays.sort, napisati sopstveni metod koji radi
  14 sortiranje.  Koristiti proizvoljnu metodu za sortiranje, a preporucuje se
  15 jedna od elementarnih metoda koje su opisane nize.
  16
  17
  18 napraviti komparatore
  19 ---------------------
  20
  21 komparatori su klase koje uporedjuju elemente neke druge klase.  Ovako se
  22 omogucava da se isti objekti mogu porediti na razlicite nacine, a ne samo na
  23 nacin definisan u `compareTo` metodu klase.
  24
  25 Da se ovakav komparator koristi u `Arrays.sort` treba dodati njegovu
  26 instancu kao drugi parametar u pozivu metod, na primer
  27
  28    Arrays.sort(mojNiz, new MojKomparatorNizova())
  29
  30 Da bi se komparator koristio u sopstvenom metodu isto se moze definisati
  31 drugi parametar tipa Comparator ciji metod `compare` ce se onda pozivati u
  32 kodu umesto `compareTo` na objektu.  Na primer
  33
  34    //umesto
  35    if (o.compareTo(o2)>0)
  36    //koristiti
  37    if (comp.compare(o,o2)>0)
  38
  39
  40 ponuditi korisniku izbor sortiranja
  41 -----------------------------------
  42
  43 Ponuditi korisniku da bira po cemu ce biti sortiran niz i na osnovu
  44 odabira koristiti odgovarajuci komparator za sortiranje.
  45
  46 Ponuditi bar sledece opcije:
  47 - id
  48 - naslov
  49 - autor
  50 - autor/naslov
  51
  52
  53 Metode sortiranja
  54 ============================================================
  55
  56 Postoje tri elementarne metode sortiranja.
  57
  58
  59 Sortiranje umetanjem (insertion)
  60 ------------------------------------------------------------
  61
  62 Pretpostavimo da je pocetak niza sortiran. Prvi element iz
  63 nesortiranog dela niza ubacujemo u sortirani deo na
  64 odgovarajuce mesto i to ponavljamo dokle god ne dodjemo do
  65 kraja niza.
  66
  67
  68 Sortiranje izabiranjem (selection)
  69 ------------------------------------------------------------
  70
  71 Pretpostavimo da je pocetak niza, prvih K elemenata,
  72 sortiran i da je u njemu K najmanjih elemenata. U
  73 nesortiranom delu niza nadjemo najmanji element i postavimo
  74 ga na pocetak nesortiranog dela.
  75
  76
  77 Sortiranje razmenom (exchange)
  78 ------------------------------------------------------------
  79
  80 Pretpostavimo da je pocetak niza, prvih K elemenata,
  81 sortiran i da je u njemu K najmanjih elemenata. Prolazimo
  82 kroz nesortirani deo, od kraja prema pocetku i za svaka dva
  83 elementa razmenimo mesta ako "stoje pogresno".
  84
  85 Takodje je poznato pod imenom "Bubble sort".
  86
  87
  88 Poredjenje metoda
  89 ============================================================
  90
  91 Sortiranje razmenom u opstem slucaju daje najgore rezultate.
  92
  93 Sortiranje izabiranjem je najbolje ukoliko su elementi niza
  94 veliki, odnosno ako je operacija poredjenja brza od
  95 premestanja elemenata u nizu.
  96
  97 Sortiranje umetanjem daje najbolje rezultate ukoliko su
  98 elementi niza mali ili je poredjenje komplikovano, tj ako
  99 je premestanje brze od poredjenja.