Kādus šķirošanas veidus jūs zināt un kādas ir to grūtības laika un atmiņas ziņā?

Ir daudz dažādu kārtošanas algoritmu, šeit ir galvenie ar to laika un atmiņas sarežģītību:

• Burbulis (Bubble Sort)

  • Laiks: O(n²) sliktākajā un vidējā gadījumā
  • Atmiņa: O(1) (kārtošana vietā)

• Ievietošanas (Insertion Sort)

  • Laiks: O(n²) sliktākajā gadījumā, O(n) labākajā (teju kārtots masīvs)
  • Atmiņa: O(1)

• Atlases (Selection Sort)

  • Laiks: O(n²) visos gadījumos
  • Atmiņa: O(1)

• Apvienošanas (Merge Sort)

  • Laiks: O(n log n) visos gadījumos
  • Atmiņa: O(n) (prasa papildu atmiņu apvienošanai)

• Ātrā (Quick Sort)

  • Laiks: O(n log n) vidēji, O(n²) sliktākajā gadījumā (retāk)
  • Atmiņa: O(log n) (rekursīvs steks)

• Hīrta (Heap Sort)

  • Laiks: O(n log n) visos gadījumos
  • Atmiņa: O(1)

• Timsort — hibrīda kārtošanas algoritms, ko izmanto Python un Java

  • Laiks: O(n log n) vidēji un sliktākajā gadījumā
  • Atmiņa: O(n)

Algoritma izvēle ir atkarīga no datu apjoma, atmiņas prasībām un stabilitātes (vai saglabā vienādu elementu kārtību). Piemēram, Merge Sort ir stabils, Quick Sort parasti ir ātrāks, bet nestabils.