Τι είναι οι αλγόριθμοι ταξινόμησης
Οι αλγόριθμοι ταξινόμησης είναι ένα σύνολο αλγορίθμων που μας βοηθούν στην ταξινόμηση των δεδομένων σε αύξουσα ή φθίνουσα σειρά. Είναι θεμελιώδεις αλγόριθμοι της επιστήμης της πληροφορικής και οι διαφορές μεταξύ τους είναι κυρίως η χρονική πολυπλοκότητα (time complexity) και οι απαιτήσεις σε μνήμη (space complexity) που κάνει κάποιους από αυτούς κατάλληλους για μεγαλύτερα σετ δεδομένων.
Bubble Sort
Ο πιο απλός αλγόριθμος ταξινόμησης και ταυτόχρονα ο χειρότερος αλγόριθμος ταξινόμησης είναι η ταξινόμηση φυσαλίδας. Στο bubble sort ξεκινάμε από την αρχή των δεδομένων μας και συγκρίνουμε τα 2 πρώτα στοιχεία. Το μικρότερο από τα δύο το βάζουμε πρώτο και το άλλο στοιχείο δεύτερο. Μετά συγκρίνουμε τα 2 επόμενα και κάνουμε το ίδιο. Επαναλαμβάνουμε μέχρι να τελειώσουν τα δεδομένα μας. Μόλις γίνει αυτό κάνουμε ξανά όλη τη διαδικασία μέχρι να ταξινομηθούν όλα μας τα δεδομένα.
Ένα παράδειγμα θα ήταν το εξής. Έστω πως έχουμε τον πίνακα με τα στοιχεία [10, 4, 5, 8, 0]. Για να εκτελέσουμε τον αλγόριθμο συγκρίνουμε το 10 με το 4. Το 4 είναι μικρότερο του 10 άρα ο πίνακας θα γίνει [4, 10, 5, 8, 0]. Στη συνέχεια συγκρίνουμε το 10 με το 5. Το 5 είναι μικρότερο του 10 άρα ο πίνακας μας θα γίνει [4, 5, 10, 8, 0]. Το επόμενο ζευγάρι είναι το 10 με το 8 άρα έχουμε [4, 5, 8, 10, 0]. Τελικά, στο πρώτο πέρασμα των δεδομένων μας ο πίνακας μας θα είναι [4, 5, 8, 0, 10]. Επαναλαμβάνουμε τη διαδικασία μέχρι ο πίνακας να είναι πλήρως ταξινομημένος.
Κώδικας
Πολυπλοκότητα του αλγορίθμου
Έχει χρόνο εκτέλεσης στη χειρότερη περίπτωση, όπου είναι ο αριθμός των στοιχείων. Αυτό κάνει τον αλγόριθμο απαγορευτικό για μεγάλα σετ δεδομένων.