Jaké druhy třídění znáte a jaké mají obtíže z hlediska času a paměti?

Existuje mnoho třídicích algoritmů, zde jsou hlavní s jejich časovou a prostorovou složitostí:

• Bubble Sort (Bublinkové třídění)

  • Čas: O(n²) v nejhorším a průměrném případě
  • Paměť: O(1) (třídění na místě)

• Insertion Sort (Vkládací třídění)

  • Čas: O(n²) v nejhorším případě, O(n) v nejlepším (téměř seřazený pole)
  • Paměť: O(1)

• Selection Sort (Výběrové třídění)

  • Čas: O(n²) ve všech případech
  • Paměť: O(1)

• Merge Sort (Sloučení třídění)

  • Čas: O(n log n) ve všech případech
  • Paměť: O(n) (vyžaduje dodatečnou paměť pro sloučení)

• Quick Sort (Rychlé třídění)

  • Čas: O(n log n) v průměru, O(n²) v nejhorším případě (zřídka)
  • Paměť: O(log n) (rekurzivní zásobník)

• Heap Sort (Hromadné třídění)

  • Čas: O(n log n) ve všech případech
  • Paměť: O(1)

• Timsort — hybridní třídicí algoritmus používaný v Pythonu a Javě

  • Čas: O(n log n) v průměru a v nejhorším případě
  • Paměť: O(n)

Výběr algoritmu závisí na velikosti dat, požadavcích na paměť a stabilitě třídění (zachovává-li pořadí rovnosti prvků). Například Merge Sort je stabilní, Quick Sort je obvykle rychlejší, ale nestabilní.