Ce tipuri de sortări cunoști și care sunt dificultățile lor în timp și memorie?

Există numeroși algoritmi de sortare, iată principalele dintre ei, împreună cu complexitatea lor temporală și spațială:

• Sortarea cu bule (Bubble Sort)

  • Timp: O(n²) în cel mai rău și mediu caz
  • Memorie: O(1) (sortare în loc)

• Sortarea prin inserție (Insertion Sort)

  • Timp: O(n²) în cel mai rău caz, O(n) în cel mai bun (array aproape sortat)
  • Memorie: O(1)

• Sortarea prin selecție (Selection Sort)

  • Timp: O(n²) în toate cazurile
  • Memorie: O(1)

• Sortarea prin fuziune (Merge Sort)

  • Timp: O(n log n) în toate cazurile
  • Memorie: O(n) (necesită memorie suplimentară pentru fuziune)

• Sortarea rapidă (Quick Sort)

  • Timp: O(n log n) în medie, O(n²) în cel mai rău caz (rar)
  • Memorie: O(log n) (stivă recursivă)

• Sortarea prin heap (Heap Sort)

  • Timp: O(n log n) în toate cazurile
  • Memorie: O(1)

• Timsort — algoritm de sortare hibrid folosit în Python și Java

  • Timp: O(n log n) în medie și în cel mai rău caz
  • Memorie: O(n)

Alegerea algoritmului depinde de dimensiunea datelor, de cerințele de memorie și de stabilitatea sortării (dacă păstrează ordinea elementelor egale). De exemplu, Merge Sort este stabil, Quick Sort este de obicei mai rapid, dar instabil.