Kokius rūšies rūšiuojimus žinote ir kokios jų sunkumai laiko ir atminties požiūriu?

Yra daugybė rūšiavimo algoritmų, čia yra pagrindiniai su jų laiko ir erdvės sudėtingumu:

• Burbulinis rūšiavimas (Bubble Sort)

  • Laikas: O(n²) blogiausiu ir vidutiniu atveju
  • Atmintis: O(1) (vietoje rūšiavimas)

• Įterpimo rūšiavimas (Insertion Sort)

  • Laikas: O(n²) blogiausiu atveju, O(n) geriausiu (beveik surūšiuotas masyvas)
  • Atmintis: O(1)

• Pasirinkimo rūšiavimas (Selection Sort)

  • Laikas: O(n²) visuomet
  • Atmintis: O(1)

• Suplakymo rūšiavimas (Merge Sort)

  • Laikas: O(n log n) visuomet
  • Atmintis: O(n) (reikalauja papildomos atminties sujungimui)

• Greitas rūšiavimas (Quick Sort)

  • Laikas: O(n log n) vidutiniškai, O(n²) blogiausiu atveju (retai)
  • Atmintis: O(log n) (rekursinis krūva)

• Kepyklos rūšiavimas (Heap Sort)

  • Laikas: O(n log n) visuomet
  • Atmintis: O(1)

• Timsort — hibridinis rūšiavimo algoritmas, naudojamas Python ir Java

  • Laikas: O(n log n) vidutiniškai ir blogiausiu atveju
  • Atmintis: O(n)

Algoritmo pasirinkimas priklauso nuo duomenų dydžio, atminties reikalavimų ir stabilumo (ar išlaiko lygiai vertingų elementų tvarką). Pavyzdžiui, Merge Sort yra stabilus, Quick Sort dažniausiai yra greitesnis, bet nestabilus.