Milliseid sorte teate ja millised on nende raskused aja ja mälu osas?

On palju sorteerimisalgoritme, siin on peamised koos nende ajakulu ja ruumilise keerukusega:

• Pallide sorteerimine (Bubble Sort)

  • Aeg: O(n²) halvimal ja keskmisel juhul
  • Mälu: O(1) (sorteerimine kohapeal)

• Sisestamise sorteerimine (Insertion Sort)

  • Aeg: O(n²) halvimal juhul, O(n) parimal juhul (peaaegu sorteeritud massiiv)
  • Mälu: O(1)

• Valimise sorteerimine (Selection Sort)

  • Aeg: O(n²) kõigis juhtumites
  • Mälu: O(1)

• Lõimimise sorteerimine (Merge Sort)

  • Aeg: O(n log n) kõigis juhtumites
  • Mälu: O(n) (vajab täiendavat mälu ühendamiseks)

• Kiire sorteerimine (Quick Sort)

  • Aeg: O(n log n) keskmiselt, O(n²) halvimal juhul (harva)
  • Mälu: O(log n) (rekursiivne virn)

• Kuhja sorteerimine (Heap Sort)

  • Aeg: O(n log n) kõigis juhtumites
  • Mälu: O(1)

• Timsort — hübriidsorteerimisalgoritm, mida kasutatakse Pythonis ja Java-s

  • Aeg: O(n log n) keskmiselt ja halvimal juhul
  • Mälu: O(n)

Algoritmi valik sõltub andmete suurusest, mäe nõuetest ja sorteerimise stabiilsusest (kas säilitab võrdsete elementide järjekorra). Näiteks on Merge Sort stabiilne, Quick Sort tavaliselt kiirem, kuid mitte stabiilne.