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

Přednáška 7 v oddíle Přednášky.

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

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

Prohlédněte si vizuální animované srovnání různých řadících algoritmů.

Ř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á ú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).

1. (Franta, 32)
2. (Pepa, 17)
3. (Petr, 25)
4. (Jana, 23)
5. (David, 23)
6. (Martina, 25)
7. (Lojza, 7)
8. (Hanka, 23)

Řešení (rozbalit)

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

Ř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í?

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;
}

Řešení (rozbalit)

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

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

Ř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í

1. Selection sortu
2. Insert sortu
3. Quick sortu

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

Řešení (rozbalit)

Ú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ěď:

Úloha 8: 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í?

Úloha 9: 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í?

Ú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í?

Ú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)$

Úloha 12: 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í.

Úloha 13: 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ě.