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
odpovídá vzestupně a hodnota 2
sestupně seřazené posloupnosti. Pokud posloupnost seřazena není, je tato hodnota 0
.
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.
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 není kladné!
– 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.
sort
, sorted
, qsort
apod.). Systém použití těchto funkcí kontroluje a takováto řešení jsou z hodnocení automaticky vyloučena.
Vyhněte se používání uvedených klíčových slov i ve vlastním kódu programu!!!
BufferedReader
(pozor, vysokoúrovňový Scanner
je příliš pomalý). Pro zápis výsledku můžete použít například následující kód:
public static void printResult(int[] s) { PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out)); for(int e : s) pw.println(e); pw.close(); }
Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
---|---|---|---|
0 1 0 10 10 | žádný | Error: Maximum neni kladne! | 1 |
Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
---|---|---|---|
10 3 2 10 5 1 | žádný | Error: Neznamy typ razeni posloupnosti! | 1 |
Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
---|---|---|---|
10 0 2 10 5 1 | žádný | Error: Nelze urcit, zda posloupnost napadl virus! | 1 |
Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
---|---|---|---|
10 0 0 11 0 5 1 | žádný | Error: Prvek posloupnosti je mimo rozsah! | 1 |
Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
---|---|---|---|
10 2 0 10 1 5 1 | žádný | Error: Posloupnost neni usporadana! | 1 |
Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
---|---|---|---|
10 0 0 10 1 5 1 | žádný | Error: Posloupnost ma mene nez 1000 prvku! | 1 |
Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
---|---|---|---|
9909 1 0 14 33 51 52 70 … seřazená posloupnost 1000 prvků | 14 33 51 52 70 … Seřazená posloupnost ze vstupu | žádný | 0 |
Vstup (stdin) | Výstup (stdout) | Chybový výstup (strerr) | Návratová hodnota |
---|---|---|---|
10 0 0 5 1 8 … neseřazená posloupnost 1000 prvků | 1 1 1 1 … Seřazená posloupnost na vstupu | žádný | 0 |
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
Java
, Python
nebo C/C++
.
Veřejné testovací soubory - DSA_HW02.
Název úlohy v BRUTE | HW02 | |
---|---|---|
Odevzdávané soubory | sort.py – zdrojový soubor v python3 |
|
Sort.java – zdrojový soubor v Java, název třídy Sort |
||
sort.c , resp. sort.cpp – zdrojový soubor v C/Cpp |
||
Argumenty programu | žádné | |
Kompilace pro jazyk C | clang -Wall -Werror -pedantic -std=c99 clang -Wall -Werror -pedantic -std=c+ +17 |
|
Kompilace a spuštění pro jazyk Java | javac *.java java -classpath Sort |
|
Očekávaná složitost | Změna velikosti tabulky, vkládání, mazání – vše v čase $\mathcal{O}(n^2)$ | |
Procvičované oblasti | řadící algoritmy složitost řadících algoritmů |
|
Bodové hodnocení (celkem 6 bodů) | 1 bod | sort_1_01 – sort_1_08 + 3 skryté testy |
2 body | sort_2_01 – sort_2_08 | |
3 body | sort_3_01 – sort_3_06 – řešení časově stejné nebo lepší než referenční řešení | |
Maximální počet uploadů | 20 Více uploadů je možných s odpovídající bodovou ztrátou |