Preskoči na glavno vsebino
Učilnica FRI 23/24
  • Domov
  • Več
Zapri
Preklopi iskalni vnos
Slovenščina ‎(sl)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
Trenutno uporabljate gostujoči dostop
Prijavite se
Domov
Course Activities
Forumi Kvizi Naloge Viri
Nedavno dostopani predmeti
You are not enrolled in any courses
  1. aps2uni
  2. Izziv 2

Izziv 2

Zahteve zaključka
Odprto: ponedeljek, 11. marec 2024, 07.00
Rok za oddajo: nedelja, 17. marec 2024, 23.59

Implementirajte program (v programskem jeziku Java), ki bo štel primerjave pri iskanju $k$-tega elementa (quickselect) z uporabo različni strategij za izbiro delilnega elementa (pivota). Štejte vsako primerjavo, kjer je udeležen nek element tabele.

Implementirajte štiri strategije izbire pivota:

1. prvi element v tabeli

2. naključni element v tabeli

3. srednji element izmed treh naključno izbranih

4. mediana (pivot dobljen z algoritmom mediana median)


Testiranje:

Testirali boste delovanje teh strategij na dveh različnih vrstah tabel. Prva vrsta bodo naključno generirane tabele, druga vrsta pa že urejene tabele.

Za neko tabelo dolžine n generirajte 10% pozicij (k) elementov, ki bi jih radi našli (iščemo torej k-ti element) . Npr. za neko tabelo dolžine 1000, generirajte 100 naključnih števil med 1 in 1000 (to je naš k) in poiščite k-ti elementov v tabeli. Pri vsakem iskanju beležite koliko primerjav je bilo narejenih, na koncu pa izračunajte povprečno število primerjav.

Pri naključnih tabelah za neko dolžino n generirajte 1000 takih testiranj, vsakič z drugo naključno tabelo, končni rezultat pa bo povprečno število primerjav preko vseh teh tabel.

Pri urejeni tabeli je lahko primer zgolj eden (ni potrebno generirati velikega števila tabel in jih urejati, lahko delate s tabelo od 1 do n), še vedno pa naj velja, da preizkusite poiskati 10% naključnih pozicij v tej tabeli.


Izhod:

Na standardni izhod izpišite dve tabeli:

1. tabela povprečnega števila primerjav pri naključnih tabelah (za vse strategije, za velikosti tabel 100, 1000, 10000 in 100000)

2. tabela povprečnega števila primerjav pri že urejenih tabelah (za vse strategije, za velikosti tabel 100, 1000, 10000 in 100000)

Primer formata tabele (zgolj za razumevanje, lahko format prilagodite svojim željam):


10^210^310^410^5
prviXXXX
naključniXXXX
mediana trehXXXX
mediana medianXXXX

Pri čemer X označuje meritve, ki jih boste dobili.







◄ Kviz 2
Prosojnice ►
Trenutno uporabljate gostujoči dostop (Prijavite se)
Pridobi mobilno aplikacijo Obvestilo o avtorskih pravicah
Stran poganja Moodle