Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

HW02 Řadící algoritmy

 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:

  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.

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

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.

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.
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!!!

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ěť. Ideálně doporučujeme načíst celý vstup najednou pomocí třídy BufferedInputStream a následně vstup vhodně parsovat v paměti. Podobně výstup je vhodné připravit si v paměti do výstupního streamu BufferedOutputStream a následně ho celý najednou vypsat na standardní výstup pomocí metody flush.
Při čtení vstupu pomocí bufferu je nutné si uvědomit, že konec řádku je obvykle značen rozdílně s ohledem na operační systém:
  1. znakem 0x0A (znak '\n' ) - znak konce řádku, tj. konec řádku je jeden bajt,
  2. dvěma znaky 0x0D 0X0A - konec řádku jsou dva bajty.

Kontrolní testy

Testovací soubory najdete zde.

Základní formát vstupu

Příklad 1 – sort_1_01

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

Příklad 2 – sort_1_02

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

Příklad 3 – sort_1_03

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

Příklad 4 – sort_1_04

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

Příklad 5 – sort_1_05

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

Příklad 6 – sort_1_06

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

Příklad 7 – sort_1_07

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

Příklad 8 – sort_1_08

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

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

Příklad 17 – sort_2_09

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

Odevzdání a hodnocení

Úlohu je možné řešit v programovacím jazyce 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 Podle druhu řadícího algoritmu – vše v čase $\mathcal{O}(n)$ až $\mathcal{O}(n \log_2 n)$
Koeficient pro čas výpočtu $1.5$
Procvičované oblasti
řadící algoritmy
složitost řadících algoritmů
Bodové hodnocení (celkem 10 bodů) 2 body sort_1_01 – sort_1_08 + 3 skryté testy
3 body sort_2_01 – sort_2_09
5 bodů sort_3_01 – sort_3_15 – ř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
courses/b6b36dsa/ukoly/hw02.txt · Last modified: 2023/07/21 09:33 by nagyoing