Program zasadniczo wczytuje dane z zadanego pliku w zadanym zakresie,
wykonuje ich sortowanie zadanym algorytmem, i wyprowadza posortowane dane
na wyjście stdout.
Dodatkowo, program powinien mierzyć czas sortowania. Ten czas należy
przeliczyć na poprawne jednostki (mikro- lub milisekundy, albo sekundy, w
zależności od tego która z tych jednostek zostanie osiągnięta), poprawnie
zaokrąglić do 3-4 cyfr znaczących, i wyświetlić na końcu krótkim
komunikatem wysłanym na wyjście stderr. Obliczenie czasu powinno
obejmować całą procedurę sortowania, włącznie z inicjalizacją pętli,
wywołaniem odpowiednich funkcji, itp. Nie powinno natomiast obejmować
wczytywania danych wejściowych ani wypisywania danych wynikowych, wstępnej
alokacji struktur, itp.
W wysłanym na stderr komunikacie należy również podać wygenerowane i
użyte w programie do mieszania tablicy ziarno generatora liczb losowych
(patrz parametr shuffle_seed poniżej).
Opracowany program powinien odczytywać następujące pozycyjne parametry wywołania:
prog input_file_name sort_key_pos n_items algo_name shuffle_passes shuffle_seed
Wyjaśnienia poszczególnych parametrów:
input_file_name zadaje nazwę pliku z którego należy pobierać dane.
Wiersz danych w pliku może być zakończony znakiem ^J (ASCII 10, styl
Uniksowy), albo sekwencją ^M^J (ASCII 13, ASCII 10, styl DOS/Windows).
Może to mieć znaczenie przy parsowaniu ostatniego pola w pliku.
Dodatkowo, jeżeli nazwa pliku wejściowego będzie zadana jako "-"
(pojedynczy znak minus), to nie należy otwierać żadnego pliku na dysku,
tylko dane wejściowe odczytywać ze standardowego wejścia stdin.
sort_key_pos zadaje numer pola w pliku wejściowym które stanowi klucz
sortowania. Numery pola liczymy od 1. To znaczy, że w zadanym pliku
danych ten numer wynosi 3, ale może być inny w innych plikach.
WAŻNE: przyjmujemy, że separatorem pól w pliku wejściowym zawsze będzie
daszek "^" (ASCII 94). To jest jedyny znak specjalny ASCII, który nie
występuje w tytułach filmów, i pozwala na łatwe parsowanie.
n_items zadaje liczbę elementów, które należy wczytać do pamięci i
sortować. Jeżeli ta liczba jest mniejsza od liczby danych w pliku
wejściowym, to wczytujemy tylko pierwsze n_items pozycji i pozostałe
dane z pliku ignorujemy. Jeżeli ta liczba jest większa niż liczba
danych w pliku po odfiltrowaniu niepoprawnych, to wypełniamy dokładnie
n_items elementów tablicy powielając początkowo wczytane elementy.
algo_name zadaje nazwę algorytmu sortowania z poniższej listy:
BUBBLE, INSERT, HEAP, MERGE, SHELL, QUICK, INTRO, BUCKET
shuffle_passes parametr opcjonalny; jeśli istnieje, to zadaje liczbę
przebiegów mieszania, które należy wykonać na danych wczytanych z pliku
(po odfiltrowaniu niepoprawnych elementów).
Jeden przebieg mieszania polega na przejściu całej tablicy i zamianie
każdego elementu z innym losowo wybranym elementem tablicy. Mieszanie
tablicy należy wykonać w miejscu, czyli bez kopiowania całej
tablicy. Nie należy też uwzględniać etapu mieszania tablicy do pomiaru
czasu sortowania.
Jeśli ten parametr nie zostanie zadany to nie wykonujemy mieszania.
To znaczy, wykonujemy sortowanie danych dokładnie w kolejności wczytania
z pliku. Inaczej, domyślną wartością tego parametru jest zero.
shuffle_seed parametr opcjonalny; jeśli istnieje, to zadaje ziarno
generatora liczb losowych które należy użyć do zainicjowania generatora
liczb pseudolosowych przed mieszaniem pliku. Oznacza to, że wielokrotne
wywołanie programu z tą samą wartością ziarna wykona identyczne
mieszanie i sortowaniu będzie podlegała zawsze ta sama sekwencja
danych.
Jeśli ten parametr nie zostanie zadany, to ziarno należy wygenerować w
sposób przypadkowy. Proszę postarać się wygenerować je taką metodą, aby
każde wywołanie programu z bardzo dużym prawdopodobieństwem otrzymało
inne ziarno.