Ποια είδη ταξινόμησης γνωρίζετε και ποιες είναι οι δυσκολίες τους σε χρόνο και μνήμη;

Υπάρχουν πολλαπλοί αλγόριθμοι ταξινόμησης, εδώ είναι οι βασικοί με την χρονική και χωρική τους πολυπλοκότητα:

• Bubble Sort (Ταξινόμηση με φούσκες)

  • Χρόνος: O(n²) στην χειρότερη και μέση περίπτωση
  • Μνήμη: O(1) (ταξινόμηση εντός του χώρου)

• Insertion Sort (Εισαγωγική ταξινόμηση)

  • Χρόνος: O(n²) στην χειρότερη περίπτωση, O(n) στην καλύτερη (σχεδόν ταξινομημένος πίνακας)
  • Μνήμη: O(1)

• Selection Sort (Επιλογή ταξινόμησης)

  • Χρόνος: O(n²) σε όλες τις περιπτώσεις
  • Μνήμη: O(1)

• Merge Sort (Συνένωση ταξινόμησης)

  • Χρόνος: O(n log n) σε όλες τις περιπτώσεις
  • Μνήμη: O(n) (απαιτεί επιπλέον μνήμη για τη συνένωση)

• Quick Sort (Γρήγορη ταξινόμηση)

  • Χρόνος: O(n log n) κατά μέσο όρο, O(n²) στην χειρότερη περίπτωση (σπάνια)
  • Μνήμη: O(log n) (αναδρομική στοίβα)

• Heap Sort (Ταξινόμηση με σωρό)

  • Χρόνος: O(n log n) σε όλες τις περιπτώσεις
  • Μνήμη: O(1)

• Timsort — υβριδική ταξινόμηση που χρησιμοποιείται σε Python και Java

  • Χρόνος: O(n log n) κατά μέσο όρο και στην χειρότερη περίπτωση
  • Μνήμη: O(n)

Η επιλογή του αλγορίθμου εξαρτάται από το μέγεθος των δεδομένων, τις απαιτήσεις μνήμης και την σταθερότητα της ταξινόμησης (αν διατηρεί τη σειρά των ίσων στοιχείων). Για παράδειγμα, το Merge Sort είναι σταθερό, το Quick Sort είναι συνήθως πιο γρήγορο, αλλά όχι σταθερό.