Welke sorteermethoden ken je en wat zijn hun moeilijkheden qua tijd en geheugen?

Er zijn veel sorteeralgoritmen, hier zijn de belangrijkste met hun tijds- en ruimtecomplexiteit:

• Bubble Sort (Bubbelsortering)

  • Tijd: O(n²) in het slechtste en gemiddelde geval
  • Geheugen: O(1) (in-place sortering)

• Insertion Sort (Invoegsortering)

  • Tijd: O(n²) in het slechtste geval, O(n) in het beste (bijna gesorteerde array)
  • Geheugen: O(1)

• Selection Sort (Selectiesortering)

  • Tijd: O(n²) in alle gevallen
  • Geheugen: O(1)

• Merge Sort (Samenvoegsortering)

  • Tijd: O(n log n) in alle gevallen
  • Geheugen: O(n) (vereist extra geheugen voor samenvoeging)

• Quick Sort (Snelsortering)

  • Tijd: O(n log n) gemiddeld, O(n²) in het slechtste geval (zelden)
  • Geheugen: O(log n) (recursieve stack)

• Heap Sort (Heap sortering)

  • Tijd: O(n log n) in alle gevallen
  • Geheugen: O(1)

• Timsort — hybride sorteeralgoritme gebruikt in Python en Java

  • Tijd: O(n log n) gemiddeld en in het slechtste geval
  • Geheugen: O(n)

De keuze van het algoritme hangt af van de grootte van de gegevens, de geheugenvereisten en de stabiliteit van de sortering (of het de volgorde van gelijke elementen behoudt). Bijvoorbeeld, Merge Sort is stabiel, Quick Sort is meestal sneller, maar niet stabiel.