třídění?

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(n²)

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 Pythonu

def 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(n²), 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.