Izziv 2

V programskem jeziku java ali C++ napišite program, ki bo štel primerjave pri iskanju $k$-tega elementa z algoritmom quickselect ob uporabi različnih 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. algoritem mediane median.

Testiranje:

Testirali boste delovanje teh strategij na dveh različnih vrstah tabel. Prva vrsta bodo naključno generirane tabele, druga pa naraščajoč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). Na primer, za tabelo dolžine 1000 generirajte 100 naključnih števil med 1 in 1000 (vsako od teh števil je naš $k$) in poiščite $k$-ti element v tabeli. Pri vsakem iskanju zabeležite število primerjav, na koncu pa izračunajte povprečno število primerjav.

Pri naključnih tabelah celoten postopek ponovite 10-krat, vsakokrat z drugo naključno tabelo.

Izhod:

Na standardni izhod izpišite dve tabeli:

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

2. tabela povprečnega števila primerjav pri naraščajoče urejenih tabelah (za vse strategije in za velikosti tabel 100, 500, 1000 in 5000).

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

V tej tabeli X označuje meritve, ki jih boste dobili.