Zadania – PK (2022)

Piotr Potiopa (zestaw nr 6)

Zadanie

Opracuj algorytm wyszukiwania oparty na QuickSelect, który znajdzie k-ty największy element w zbiorze liczb. Program ma działać w następujący sposób:

1. program przy uruchomieniu z parametrem „-random” powinien wygenerować n losowych, unikalnych liczb (liczby od 0 do 1000 0000), które będą zapisane w pliku random.txt.

(liczba n podawana jest na wejściu programu w zakresie od 0 do 100 000)

2. Po uruchomieniu programu bez parametru „-random” program powinien zaczytać plik random.txt, gdzie zapisane są liczby losowe i zapytać o parametr k.

3. następnie wyliczyć k-ty największy element, bazując na zbiorze liczb z pliku,

i wypisać go na ekran. Program powinien dodatkowo pokazywać czas wykonania operacji wyszukiwania (po wczytaniu danych, czyli sama operacja wyszukiwania). Proszę też o zapisanie czasu wyszukiwania dla liczby n = 100 000.

Uwaga: jeśli algorytm wymaga posortowanych liczb trzeba to obsłużyć już na etapie generowania liczb do pliku random.txt.

Przydatne linki:
https://en.wikipedia.org/wiki/Quickselect