Ταξινόμηση Φυσαλίδας (Bubble Sort)
Η ταξινόμηση φυσαλίδας συγκρίνει διαδοχικά ζεύγη γειτονικών στοιχείων και τα ανταλλάσσει αν δεν είναι στη σωστή σειρά. Μετά από κάθε πλήρη πέρασμα, το μεγαλύτερο στοιχείο «ανεβαίνει» στη σωστή θέση στο τέλος του πίνακα.
- Βασική Ιδέα:
- Συγκρίνουμε συνεχώς διπλανά στοιχεία.
- Αν είναι σε λάθος σειρά, τα ανταλλάσσουμε.
- Σε κάθε πέρασμα, το επόμενο μεγαλύτερο στοιχείο τοποθετείται στη θέση του.
- Σταματά: Όταν δεν χρειάζονται άλλες ανταλλαγές.
- Πολυπλοκότητα:
- Χειρότερη περίπτωση: O(n²).
- Χρειάζεται δύο εμφωλευμένους βρόχους.
- Πλεονεκτήματα: Απλή στην κατανόηση.
- Μειονεκτήματα: Αργή για μεγάλα σύνολα δεδομένων.
Ταξινόμηση Επιλογής (Selection Sort)
Η ταξινόμηση επιλογής βρίσκει κάθε φορά το μικρότερο στοιχείο του πίνακα και το τοποθετεί στην αρχή, στη σωστή θέση. Αυτό επαναλαμβάνεται για όλα τα στοιχεία μέχρι να ταξινομηθεί ο πίνακας.
- Βασική Ιδέα:
- Εντοπίζουμε το ελάχιστο στοιχείο.
- Το ανταλλάσσουμε με το στοιχείο της τρέχουσας θέσης.
- Μετακινήσεις: Ελάχιστες, καθώς αλλάζουμε θέση μόνο στο στοιχείο που είναι το ελάχιστο.
- Πολυπλοκότητα:
- O(n²) συγκρίσεις.
- Δύο εμφωλευμένοι βρόχοι: ένας για την επιλογή, ένας για τη σύγκριση.
- Πλεονεκτήματα: Λίγες μετακινήσεις στοιχείων.
- Μειονεκτήματα: Δεν είναι σταθερή μέθοδος (ίσου μεγέθους στοιχεία μπορεί να αλλάξουν σειρά).
Ταξινόμηση Εισαγωγής (Insertion Sort)
Η ταξινόμηση εισαγωγής λειτουργεί όπως όταν ταξινομούμε χαρτιά τράπουλας: κάθε νέο στοιχείο τοποθετείται στη σωστή του θέση στο ήδη ταξινομημένο τμήμα του πίνακα.
- Βασική Ιδέα:
- Ξεκινάμε από το δεύτερο στοιχείο και το συγκρίνουμε με τα προηγούμενα.
- Το εισάγουμε στη σωστή θέση μετακινώντας τα υπόλοιπα.
- Αποδοτικότητα:
- Πολύ καλή για μικρά ή ήδη σχεδόν ταξινομημένα σύνολα.
- Στην καλύτερη περίπτωση (ήδη ταξινομημένος πίνακας): O(n).
- Στη χειρότερη περίπτωση: O(n²).
- Πλεονεκτήματα: Σταθερή μέθοδος (δεν αλλάζει τη σειρά ισοδύναμων στοιχείων).
- Μειονεκτήματα: Αργή για πολύ μεγάλα και αταξινόμητα σύνολα.