Třídění – jak seřadit čísla podle velikosti
Občas se ti bude hodit umět seřadit čísla v poli podle velikosti. Přesně tomu se říká třídění.
Většina programovacích jazyků má připravenou funkci, která to udělá za tebe. Přesně tu ti doporučujeme použít, protože se nemusíš o nic starat a můžeš se plně soustředit na soutěžní úlohy. Pokud by tě zajímalo, jak se taková funkce naprogramuje, dozvíš se to níže na této stránce.
Tady jsme ti připravili pár ukázek třídění v často používaných jazycích. Dozvíš se z nich, jak čísla seřadit od nejmenšího po největší a taky jak je seřadit opačně.
Python
pole = [5, 1, 4, 2, 3]
serazene = sorted(pole) # [1, 2, 3, 4, 5]
pozpatku = sorted(pole, reverse=True) # [5, 4, 3, 2, 1]
Javascript
const pole = [5, 1, 4, 2, 3];
pole.sort(); // změní pole na [1, 2, 3, 4, 5]
pole.reverse(); // změní pole na [5, 4, 3, 2, 1] (otočí pole, setřídili jsme ho na předchozím řádku)
C#
Pole:
int[] pole = new int[]{ 5, 1, 4, 2, 3 };
Array.Sort(pole); // změní pole na [1, 2, 3, 4, 5]
Array.Reverse(pole); // změní pole na [5, 4, 3, 2, 1] (otočí pole, setřídili jsme ho na předchozím řádku)
List, ArrayList, … :
using System.Collections.Generic;
List<int> pole = new List<int>(){ 5, 1, 4, 2, 3 };
pole.Sort(); // změní pole na [1, 2, 3, 4, 5]
pole.Reverse(); // změní pole na [5, 4, 3, 2, 1] (otočí pole, setřídili jsme ho na předchozím řádku)
C++
Pole:
#include <algorithm>
int pole[] = { 5, 1, 4, 2, 3 };
int n = 5; // délka pole
std::sort(pole, pole + n); // změní pole na [1, 2, 3, 4, 5]
std::reverse(pole, pole + n); // změní pole na [5, 4, 3, 2, 1] (otočí pole, setřídili jsme ho na předchozím řádku)
Vector:
#include <algorithm>
#include <vector>
std::vector<int> pole = { 5, 1, 4, 2, 3 };
std::sort(pole.begin(), pole.end()); // změní pole na [1, 2, 3, 4, 5]
std::reverse(pole.begin(), pole.end()); // změní pole na [5, 4, 3, 2, 1] (otočí pole, setřídili jsme ho na předchozím řádku)
Java
import java.util.Arrays;
import java.util.Collections;
Integer[] pole = new Integer[] { 5, 1, 4, 2, 3 };
Arrays.sort(pole); // změní pole na [1, 2, 3, 4, 5]
Arrays.sort(pole, Collections.reverseOrder()); // změní pole na [5, 4, 3, 2, 1]
Jak ale třídění funguje?
Metod pro setřídění pole je opravdu hodně. Při vývoji algoritmů se snažíme provést výpočet co nejrychleji - přečti si článek o časové složitosti. Pomalejší metody jsou typicky jednodušší na pochopení, tak se na ně pojďme podívat.
Třídění v čase O(n2)
Tyto metody mají relativně vysokou časovou složitost, proto se v praxi moc nepoužívají. Je ale dobré je znát - resp. každý správný programátor by je znát měl, nebo by alespoň měl tušit, že něco takového existuje. V následujících příkladech budeme prvky třídit od nejmenšího po největší.
SelectSort
Tento algoritmus si udržuje nesetříděný úsek a vždy v něm najde minimum. Toto minimum pak přesuneme na začátek úseku. Tím se nesetříděný úsek zmenší o jeden prvek. Takto pokračujeme dál, dokud není nesetříděný úsek nulový, a tím pádem tedy celé pole setříděné.
Otázka zní, jak přesunout minimum z nesetříděné části pole na její začátek, kde již nějaký prvek leží. Uděláme to následovně: naše nalezené minimum prostě prohodíme s prvním prvkem v nesetříděné části pole.
Ukázka kódu v Pythonudef SelectSort(pole): # setřídí zadané pole čísel
k = 1
for i in range(0, len(pole)): # v i-tém kroku je nesetříděný úsek mezi pozicemi i a len(pole)-1
k = i # k je pozice minima z nesetříděného úseku
for j in range(i + 1, len(pole)): # procházíme nesetříděný úsek a hledáme pozici minima k
if pole[j] < pole[k]:
k = j
pole[i], pole[k] = pole[k], pole[i] # minimum z nesetříděného úseku pole[k] uložíme na i-tou pozici, kde nesetříděný úsek začíná
# zároveň prvek na i-té pozici pole[i] odložíme na k-tou pozici, kde bylo doteď uloženo minimum
Existují další třídící algoritmy se složitostí O(n2), mezi které patří například BubbleSort nebo InsertSort. Více se můžeš dovědět třeba zde.
Třídění v čase O(n log(n))
Časová složitost O(n log(n)) je opravdu dobrá. V určitém smyslu dokonce nejlepší možná. Proto se s algoritmy s touto časovou složitostí také setkáš v praxi, kde se běžně používají.
Existují dva základní algoritmy s časovou složitostí O(n log(n)) - MergeSort a QuickSort. Jelikož je toto téma již trochu pokročilé, nebudeme zde algoritmy popisovat. Dobrý zdroj, kde si o MergeSortu a Quicksortu můžeš přečíst, je zde.