Zadania – PK (2022)

Piotr Potiopa (zestaw nr 4)

Zadanie

Opracuj algorytm wyszukiwania oparty na Jump Search, który znajdzie wskazany 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 1 000 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 liczbę którą ma wyszukać.

3. Następnie przeszukać zbiór wczytanych z pliku liczb i wypisać na ekran pozycję liczby (indeks kolejności) którą szuka.

4. 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/Jump_search