Milyen rendezési típusokat ismersz, és milyen nehézségeik vannak idő és memória szempontjából?

Számos rendezési algoritmus létezik, ezek közül a főbbek a következők, azok idő- és térkomplexitásával:

• Bubble Sort (Buborékrendezés)

  • Idő: O(n²) a legrosszabb és átlagos esetben
  • Memória: O(1) (helyben rendezés)

• Insertion Sort (Beszúrásos rendezés)

  • Idő: O(n²) a legrosszabb esetben, O(n) a legjobb (majdnem rendezett tömb)
  • Memória: O(1)

• Selection Sort (Kiválasztásos rendezés)

  • Idő: O(n²) minden esetben
  • Memória: O(1)

• Merge Sort (Összefűző rendezés)

  • Idő: O(n log n) minden esetben
  • Memória: O(n) (további memóriát igényel az összefűzéshez)

• Quick Sort (Gyors rendezés)

  • Idő: Átlagosan O(n log n), a legrosszabb esetben O(n²) (ritka)
  • Memória: O(log n) (rekurzív verem)

• Heap Sort (Heap rendezés)

  • Idő: O(n log n) minden esetben
  • Memória: O(1)

• Timsort — hibrid rendezési algoritmus, amit Pythonban és Java-ban használnak

  • Idő: Átlagosan és a legrosszabb esetben O(n log n)
  • Memória: O(n)

Az algoritmus kiválasztása az adatok méretétől, memóriaigényétől és a rendezés stabilitásától függ (hogy megőrzi-e az egyenlő elemek sorrendjét). Például a Merge Sort stabil, a Quick Sort általában gyorsabb, de nem stabil.