Izziv 2

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):

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