====== 7 - Řazení $O(n^2)$ ======

/*
<WRAP info> Toto cvičení prochází úpravou, zatím využijte následující zdroje.

{{:courses:a4b33alg:cviceni05upd.pdf| pdf}}, {{:courses:a4b33alg:cviceni8resene.pdf| pdf}}

{{:courses:a4b33alg:cviceni8code.zip| zip}}, {{:courses:b4b33alg:cv8.py| python}}

{{ :courses:b4b33alg:cv_opakovani_3_az_8.pdf | opakovani}}
</WRAP>

*/

==== Připomenutí teorie ====

Přednáška 7 v oddíle [[courses:b4b33alg:prednasky|Přednášky]].

=== Selection sort ===
Selection sort probíhá tak, že vždy najdeme nejmenší prvek ve zbytku pole a zaměníme ho za první prvek za seřazenou částí pole.

Výhodu má pro řazení prvků, které vyžadují minimální počet přesunů.
{{ :courses:b4b33alg:cviceni:07_selection_sort.gif?80 |}}

{{ :courses:b4b33alg:cviceni:07_insertion_sort.gif?300|}}
=== Insert(ion) sort ===
Insert sort probíhá tak, že vždy bereme první prvek za seřazenou částí pole a postupně posouváme předchozí prvky, dokud nenajdeme prvek, který je menší (nebo nedojdeme na začátek pole). Prvek umístíme a pokračujeme dále.

Algroritmus sice provede více přesunů než Selection sort, výhodu má ale pro téměř seřazená pole, kdy nemusí dělat tolik porovnání a má tak v ideálním případě lineární složitost.


=== Quick sort ===
{{ :courses:b4b33alg:cviceni:07_quick_sort.gif?300|}}
Quick sort vybere pivota (prvek z pole) a přesune v lineárním průchodu větší prvky doprava a menší doleva. Na těchto dvou částech pole pak rekurzivně provádí to samé, dokud se nedostane k poli s jediným prvkem, které je triviálně uspořádané.

Quick sort má kvadratickou složitost jen v nejhorším případě, pokud máme neustále "smůlu" na pivoty. Jeho očekávaná složitost je $\Theta(n\log(n))$.

=== Srovnání složitostí ===
^ ^ Nejhorší případ ^ Nejlepší případ ^ Průměrný případ ^
|Selection sort | $\Theta(n^2)$ | $\Theta(n^2)$      | $\Theta(n^2)$      |
|Insertion sort | $\Theta(n^2)$ | $\Theta(n)$        | $\Theta(n^2)$      |
|Quicksort      | $\Theta(n^2)$ | $\Theta(n\log(n))$ | $\Theta(n\log(n))$ |


Prohlédněte si vizuální animované [[https://www.toptal.com/developers/sorting-algorithms | srovnání různých řadících algoritmů]].

=== Stabilita řazení ===
Řazení je stabilní, pokud prvky se stejnou hodnotou podle které řadíme zůstanou v pořadí v jakém byly v neuspořádaném poli. Toto se hodí v případě, že například máme jména seřazena podle křestních jmen a chceme je seřadit podle přijímení, přičemž chceme zachovat vzájemné uspořádání osob se stejným přijímením.

Insert sort může být stabilní, Selection sort ani Quick sort triviálně ne.
==== Řešené úlohy ====

=== Stabilita ===

**Řešená úloha 1:**
Jak seřadí následující záznamy //podle věku// stabilní řadící algoritmus? Záznamy jsou ve formátu (jméno, věk).

  - (Franta, 32)
  - (Pepa, 17)
  - (Petr, 25)
  - (Jana, 23)
  - (David, 23)
  - (Martina, 25)
  - (Lojza, 7)
  - (Hanka, 23)

++++ Řešení (rozbalit)|
  - (Lojza, 7)
  - (Pepa, 17)
  - (Jana, 23)
  - (David, 23)
  - (Hanka, 23)
  - (Petr, 25)
  - (Martina, 25)
  - (Franta, 32)
++++

**Řešená úloha 2:**
Zapište následující prvky do pole tak, aby Selection sort seřadil prvky nestabilně. Prvky řadíme abecedně, dolní index značí jen vzájemné pořadí stejných prvků.

$A, B, C_1, C_2, C_3, D$

++++ Řešení (rozbalit)|
Například $C_1, D, B, C_2, A, C_3$.
++++

-----

**Řešená úloha 3:**
Níže je uveden kód Insert sortu. Představuje stabilní řazení. Jaké změny je v něm nutno provést, aby nadále korektně řadil libovolná data a přitom nebyl stabilní?

<code java>
int insVal, j
for(int i = 1; i < a.length; i++) {
    insVal = a[i];
    j = i-1;
    while((j >= 0) && (a[j] > insVal)){
        a[j+1] = a[j];
        j--;
    }
    a[j+1] = insVal;
}
</code>

++++ Řešení (rozbalit)|
V podmínce cyklu ''while'' je potřeba nahradit ostrou nerovnost ''>'' za větší nebo rovno ''>=''.
++++

-----


=== Řazení ===

**Řešená úloha 4:**
Jedenáct prvků řadíme pomocí Insert sortu. Jaký je minimální a maximální možný počet porovnání prvků během tohoto řazení? Jak pole v obou případech vypadají?

++++ Řešení (rozbalit)|
Minimum je 10 (seřazené vzestupně) a maximum je 55 (seřazené sestupně).
++++

-----

**Řešená úloha 5:**
Následující pole se řadí pomocí Quick sortu. 

6, 10, 8, 5, 7, 2, 3, 9, 1, 4

Určete, jak bude pole rozděleno na "malé" a "velké" hodnoty po jednom průchodu, pokud jako pivotní hodnotu použijeme:

  * 6
  * 8
  * 4

++++ Řešení (rozbalit)|
  * **pro 6:** 4, 1, 3, 5, 2 **|** 7, 8, 9, 10, 6
  * **pro 8:** 6, 4, 1, 5, 7, 2, 3 **|** 9, 8, 10
  * **pro 4:** 4, 1, 3, 2 **|** 7, 5, 8, 9, 10, 6
++++

-----

**Řešená úloha 6:**
V určitém problému je velikost zpracovávaného pole s daty rovna
$2n^3 \log n$, kde $n$ charakterizuje velikost problému. Pole se řadí pomocí
  - Selection sortu
  - Insert sortu
  - Quick sortu

Jaká je asymptotická složitost jednotlivých algoritmů nad uvedeným
polem?

++++ Řešení (rozbalit)|
$\Theta(n^6 log^2 n)$ pro Selection sort

$\mathrm{O}(n^6 log^2 n)$ pro Insert a Quick sort

Pro Quick sort v průměrném případě dokonce $\Theta(n^3 log^2 n)$.
++++

-----

==== Další úlohy ====

**Úloha 7:**
Jaká posloupnost vznikne, když stabilní řadicí algoritmus seřadí posloupnost $A_2 \; C_2 \; B_2 \; B_1 \; C_1 \; A_1$, v níž platí $A_1 = A_2 < B_1 = B_2 < C_1 = C_2$.

++++Odpověď: |
$A_2 \; A_1 \; B_2 \; B_1 \; C_2 \; C_1$
++++
----

=== Insert sort pro speciální případy ===


**Úloha 8:**
{{ :courses:b4b33alg:cviceni:07_8_array.png?200|}}
Insert sort řadí (do neklesajícího pořadí) pole o $n$ prvcích, kde hodnoty od třetího do posledního prvku rostou a  hodnoty prvních dvou prvků jsou stejné a v poli největší. 

  * Kolik porovnání dvou prvků se provede během tohoto řazení?
  * Kolik celkem zápisů do řazeného pole se provede během tohoto řazení? 

/*
Počet porovnání: $ 1 + 2 + 3(n-3)$
Počet zápisů: $1 + 3(n - 2)$
*/

----

**Úloha 9:**
{{ :courses:b4b33alg:cviceni:07_9_array.png?200|}}
Insert sort řadí (do neklesajícího pořadí) pole o $n$ prvcích, kde hodnoty prvního a posledního prvku jsou stejné a vyšší než hodnoty ostatních prvků. Ostatní prvky mají rovněž stejnou hodnotu (ale menší než krajní prvky).

  * Kolik porovnání dvou prvků se provede během tohoto řazení?
  * Kolik celkem zápisů do řazeného pole se provede během tohoto řazení? 

/*
Počet porovnání: $2(n - 2)$
Počet zápisů: $2(n - 2)$
*/

----

**Úloha 10:**
Insert sort řadí (do neklesajícího pořadí) pole o $n$ prvcích,
kde v první polovině pole jsou pouze dvojky, ve druhé
polovině jsou jen jedničky.

  * Kolik porovnání dvou prvků se provede během tohoto řazení?
  * Kolik celkem zápisů do řazeného pole se provede během tohoto řazení? 

----

=== Složitost ===

**Úloha 11:**

Pole $n$ různých prvků je uspořádáno od druhého prvku sestupně, první prvek má nejmenší hodnotu ze všech prvků v poli. Vyberte níže všechny možnosti, které alespoň přibližně charakterizují asymptotickou složitost

  * Selection sortu
  * Insert sortu
  * Quick sortu

pracujícího nad tímto konkrétním polem.

 a) $O(n)$ \\
 b) $\Omega(n)$ \\
 c) $\Theta(n)$ \\
 d) $O(n^2)$ \\
 e) $\Omega(n^2)$ \\
 f) $\Theta(n^2)$
----

=== Quick sort extra ===

<wrap important>**Úloha 12:**</wrap>
Quick sort řadí pole o $n$ prvcích, které nabývají pouze
dvou hodnot, 1 a 2. Jedniček i dvojek je stejně mnoho,
ale jejich poloha není známa. Určete, jaké je jejich \\
 **A)** nejvíce příznivé, \\
 **B)** nejméně příznivé \\
rozložení v poli.

Pro případ **A)** i **B)** určete asymptotickou složitost tohoto
řazení.
----

<wrap important>**Úloha 13:**</wrap>
Předpokládejme, že vždy, když Quick sort rozdělí daný
úsek pole na "malé" a "velké" hodnoty, bude jeden z
těchto úseků třikrát delší než ten druhý.
Určete asymptotickou složitost Quick sort-u v tomto
případě.
----