Aké druhy triedenia poznáte a aké majú ťažkosti z hľadiska času a pamäti?

Existuje veľa algoritmov zoradenia, tu sú hlavné s ich časovou a priestorovou zložitosťou:

• Bubble Sort (Bublinkové zoradenie)

  • Čas: O(n²) v najhoršom a priemernom prípade
  • Pamäť: O(1) (zoradenie na mieste)

• Insertion Sort (Vkladacie zoradenie)

  • Čas: O(n²) v najhoršom prípade, O(n) v najlepšom (takmer zoradený poľom)
  • Pamäť: O(1)

• Selection Sort (Výberové zoradenie)

  • Čas: O(n²) vo všetkých prípadoch
  • Pamäť: O(1)

• Merge Sort (Zlučovacie zoradenie)

  • Čas: O(n log n) vo všetkých prípadoch
  • Pamäť: O(n) (vyžaduje dodatočnú pamäť na zlúčenie)

• Quick Sort (Rýchle zoradenie)

  • Čas: O(n log n) priemerne, O(n²) v najhoršom prípade (zriedka)
  • Pamäť: O(log n) (rekurzívny zásobník)

• Heap Sort (Hromadné zoradenie)

  • Čas: O(n log n) vo všetkých prípadoch
  • Pamäť: O(1)

• Timsort — hybridný algoritmus zoradenia používaný v Pythone a Jave

  • Čas: O(n log n) priemerne a v najhoršom prípade
  • Pamäť: O(n)

Výber algoritmu závisí od veľkosti dát, požiadaviek na pamäť a stability zoradenia (či zachováva poradie rovnakých prvkov). Napríklad Merge Sort je stabilný, Quick Sort je zvyčajne rýchlejší, ale nestabilný.