Jeroným začal studovat řadící algoritmy a řekl si, že by je bylo dobré otestovat na dlouhých posloupnostech – zda to, co říká teorie, opravdu v praxi platí. Zkonstruoval generátor posloupností, který generoval posloupnosti délky tisíc až milion prvků a současně dokázal vymezit vlastnosti vygenerované posloupnosti (maximum prvků a případně typ řazení).

Když Jeroným zkoušel svůj generátor, přišel na to, že jej napadl virus a generované posloupnosti měnily svoje vlastnosti. Virus způsoboval, že asi 10% prvků posloupnosti měnilo svoji pozici v posloupnosti o nejvýše 16 míst (index prvku se zmenšil / zvětšil o maximálně 16). Jeroným takové posloupnosti bedlivě označoval.

Pomozte Jeronýmovi vytvořit program, který dokáže co nejrychleji a nejefektivněji řadit posloupnosti celých čísel generovaných generátorem.

Na vstupu je posloupnost čísel. První řádek obsahuje hlavičku – 3 čísla oddělená mezerou a popisující vlastnosti posloupnosti:

1. Maximum (maximální hodnota) prvků posloupnosti. Například číslo 10 říká, že v posloupnosti se opakovaně vyskytují pouze čísla 1 až 10.
2. Typ řazení posloupnosti – hodnota 1 odpovídá vzestupně a hodnota 2 sestupně seřazené posloupnosti. Pokud posloupnost seřazena není, je tato hodnota 0.
3. Napadení virem (hodnota 1) či nikoliv (hodnota 0).

Na vstupu dále následují prvky posloupnosti – kladná celá čísla do maximální hodnoty 2147483647 (maximální hodnota proměnné typu int – 32-bitová reprezentace). Každé číslo je v souboru zapsané na novém řádku. Maximální počet prvků na vstupu je omezen na milion.

Výstupem je posloupnost čísel seřazená vzestupně, jednotlivá čísla jsou odřádkována. Rozhodující je efektivita řazení posloupnosti.

Vstupní soubor kompletně načtěte. Zkontrolujte, zda vygenerovaná posloupnost odpovídá zadání. Kontrola vstupu a případné vypsání chyby musí být provedeno v následujícím pořadí:

• Error: Maximum neni kladne! – maximum prvků posloupnosti je menší než 1
• Error: Neznamy typ razeni posloupnosti! – typ řazení posloupnosti není z množiny $\{0, 1, 2\}$
• Error: Nelze urcit, zda posloupnost napadl virus! – chybí informace o napadení virem nebo je zadaná chybně (mimo množinu $\{0, 1\}$)
• Error: Prvek posloupnosti je mimo rozsah! – na vstupu je v posloupnosti zadané číslo, které není kladné nebo které je větší než zadané maximum prvků posloupnosti
• Error: Posloupnost neni usporadana! – pokud je deklarováno seřazení posloupnosti a posloupnost není napadena virem, je potřeba při načítání vstupů zkontrolovat, zda je pousloupnost opravdu seřazena (sestupně, vzestupně)
• Error: Posloupnost ma mene nez 1000 prvku! – na vstupu je méně než tisíc prvků
• Error: Posloupnost ma vic nez 1000000 prvku! –– na vstupu je víc než milion prvků

Detekovanou chybu na chybovém výstupu vypište a program ukončete. Vypsané chybové hlášení je ukončeno koncem řádku (znakem \n).

Při návrhu časově optimálního algoritmu je potřeba vzít v úvahu možné typy posloupnosti – zda jsou již správně seřazené, či jsou řazené sestupně, zda jsou napadeny virem, či zda je omezeno maximum prvků posloupnosti. Tyto vlastnosti posloupností odkazují na optimální algoritmy pro jejich řazení. Implementujte všechny potřebné algoritmy a podle typu posloupnosti aplikujte na dané posloupnosti odpovídající algoritmus.

Opravu posloupnosti při jejím napadení virem lze řešit mnoha způsoby. Hledejte časově optimální z nich. Rozhodně stačí prohledat a uspořádat pouze blízké okolí každého prvku posloupnosti, i když toto okolí může být větší než ±16 prvků.

Při hledání optimálního řešení je potřeba vzít v úvahu i dobu potřebnou pro čtení dat ze vstupu a dobu pro vypsání výsledků. Tuto dobu lze zkrátit využitím vyrovnávací paměti při čtení a zápisu dat.

Dále jsou posloupnosti generovány náhodně podle daných charakteristik.

Příklad 9 – sort_2_01

Vstup: Posloupnost 10000 prvků seřazená sestupně

Příklad 10 – sort_2_02

Vstup: Posloupnost 10000 prvků seřazená vzestupně a napadena virem

Příklad 11 – sort_2_03

Vstup: Posloupnost 10000 prvků seřazená sestupně a napadena virem

Příklad 12 – sort_2_04

Vstup: Neseřazená posloupnost 10000 prvků napadena virem

Příklad 13 – sort_2_05

Vstup: Neseřazená posloupnost 10000 prvků

Příklad 14 – sort_2_06

Vstup: Neseřazená posloupnost 10000 prvků, čísla jsou v rozmezí 1 až 100

Příklad 15 – sort_2_07

Vstup: Neseřazená posloupnost 100000 prvků

Příklad 16 – sort_2_08

Vstup: Neseřazená posloupnost 100000 prvků, čísla jsou v rozmezí 1 až 1000

Příklad 17 – sort_2_09

Vstup: Posloupnost 100000 prvků seřazená sestupně a napadena virem

Veřejné testovací soubory - DSA_HW02.

clang -Wall -Werror -pedantic -std=c99
clang -Wall -Werror -pedantic -std=c+ +17

javac *.java
java -classpath Sort

řadící algoritmy
složitost řadících algoritmů