======== HW02 Řadící algoritmy ========

{{:courses:b6b36dsa:ukoly:sort.png?300 | Rychlé šípy - postavy }}

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:
  - Maximum (maximální hodnota) prvků posloupnosti. Například číslo 10 říká, že v posloupnosti se opakovaně vyskytují pouze čísla 1 až 10. 
  - Typ řazení posloupnosti – hodnota ''1'' odpovídá vzestupně a hodnota ''2'' sestupně seřazené posloupnosti. Pokud posloupnost seřazena není, je tato hodnota ''0''.
  - 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.

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


====== Kontrola vstupu ======

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'').


====== Algoritmus řešení úlohy ======

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.

<note important>Posloupnosti jsou opravdu dlouhé a jejich kompletní výpis v BRUTE je prakticky nemožný. Vypisovány jsou proto pouze části posloupností. Při chybném řazení jsou vypsány části, kde se v seřazené posloupnosti nachází první chyba – to nutně nemusí být na začátku posloupnosti.</note>

<note warning>Varujeme před používáním funkcí se standardních knihoven (například ''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!!!**</note>

<note important>
V poslední fázi hodnocení vašeho řešení testujeme časovou náročnost implementace. V některých testovacích případech je nutno uvažovat, kromě času daného řazením, i režii vstupu a výstupu. V programovacím jazyce Java je pro snížení náročnosti nutno použít metody čtení a zápisu využívající vyrovnávací paměť. Pro čtení v Javě doporučujeme použít třídu ''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:
<code java>
public static void printResult(int[] s) {
   PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));
   for(int e : s) pw.println(e);
   pw.close();
}
</code>
</note>
====== Kontrolní testy ======

<note>Testovací soubory najdete {{ :courses:b6b36dsa:ukoly:dsa_hw02.zip |zde}}.</note>
===== Základní formát vstupu =====

==== Příklad 1 – sort_1_01 ====

^  Vstup (stdin)  ^  Výstup (stdout)  ^  Chybový výstup (strerr)  ^  Návratová hodnota  ^
| <code>0 1 0
10
10</code> |  žádný  |  <code>Error: Maximum neni kladne!</code>  |  1  |

==== Příklad 2 – sort_1_02 ====

^  Vstup (stdin)  ^  Výstup (stdout)  ^  Chybový výstup (strerr)  ^  Návratová hodnota  ^
| <code>10 3 2
10
5
1</code> |  žádný  |  <code>Error: Neznamy typ razeni posloupnosti!</code>  |  1  |

==== Příklad 3 – sort_1_03 ====

^  Vstup (stdin)  ^  Výstup (stdout)  ^  Chybový výstup (strerr)  ^  Návratová hodnota  ^
| <code>10 0 2
10
5
1</code> |  žádný  |  <code>Error: Nelze urcit, zda posloupnost napadl virus!</code>  |  1  |

==== Příklad 4 – sort_1_04 ====

^  Vstup (stdin)  ^  Výstup (stdout)  ^  Chybový výstup (strerr)  ^  Návratová hodnota  ^
| <code>10 0 0
11
0
5
1</code> |  žádný  |  <code>Error: Prvek posloupnosti je mimo rozsah!</code>  |  1  |

==== Příklad 5 – sort_1_05 ====

^  Vstup (stdin)  ^  Výstup (stdout)  ^  Chybový výstup (strerr)  ^  Návratová hodnota  ^
| <code>10 2 0
10
1
5
1</code> |  žádný  |  <code>Error: Posloupnost neni usporadana!</code>  |  1  |
==== Příklad 6 – sort_1_06 ====

^  Vstup (stdin)  ^  Výstup (stdout)  ^  Chybový výstup (strerr)  ^  Návratová hodnota  ^
| <code>10 0 0
10
1
5
1</code> |  žádný  |  <code>Error: Posloupnost ma mene nez 1000 prvku!</code>  |  1  |
==== Příklad 7 – sort_1_07 ====

^  Vstup (stdin)  ^  Výstup (stdout)  ^  Chybový výstup (strerr)  ^  Návratová hodnota  ^
| <code>9909 1 0
14
33
51
52
70
… seřazená posloupnost 1000 prvků</code> |  <code>14
33
51
52
70
…
Seřazená posloupnost ze vstupu</code>  |  žádný  |  0  |
==== Příklad 8 – sort_1_08 ====

^  Vstup (stdin)  ^  Výstup (stdout)  ^  Chybový výstup (strerr)  ^  Návratová hodnota  ^
| <code>10 0 0
5
1
8
… neseřazená posloupnost 1000 prvků</code> |  <code>1
1
1
1
…
Seřazená posloupnost na vstupu</code>  |  žádný  |  0  |
===== Náhodné testy =====

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

====== Odevzdání a hodnocení ======

<note tip>Úlohu je možné řešit v programovacím jazyce ''Java'', ''Python'' nebo ''C/C++''.</note>

Veřejné testovací soubory - {{:courses:b6b36dsa:ukoly:DSA_HW02.zip?400|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 |  <code>clang -Wall -Werror -pedantic -std=c99
clang -Wall -Werror -pedantic -std=c+ +17</code> ||
^  Kompilace a spuštění \\ pro jazyk Java |  <code>javac *.java
java -classpath Sort</code> ||
^  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 | <code>řadící algoritmy
složitost řadících algoritmů</code> ||
^  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 ||