Αλγόριθμος ταξινόμησης

Στην επιστήμη των υπολογιστών ο αλγόριθμος ταξινόμησης είναι ένας αλγόριθμος που μεταθέτει τα στοιχεία μίας ακολουθίας έτσι ώστε να έχουν μία συγκεκριμένη σειρά. Παραδείγματα τέτοιων σειρών αποτελούν η αριθμητική και η αλφαβητική.

Πιο συγκεκριμένα ένας αλγόριθμος ταξινόμησης είναι ένας αλγόριθμος που δοσμένης μίας ακολουθίας εισόδου  και μίας συνάρτησης δίαταξης , παράγει μία ακολουθία εξόδου  τέτοια ώστε
:

 Η ακολουθία  αποτελεί μετάθεση της 

Η συνάρτηση  είναι αυτή που καθορίζει τη σειρά ταξινόμησης. Έτσι επιλέγοντας  η σειρά ταξινόμησης είναι η φθίνουσα.

 Βασικές έννοιες 
 Εσωτερική (internal) λέγεται η ταξινόμηση η οποία γίνεται εξ ολοκλήρου στην κύρια μνήμη.
 Εξωτερική (external) λέγεται η ταξινόμηση που γίνεται στη δευτερεύουσα μνήμη όπως για παράδειγμα στον σκληρό δίσκο. 
 Αντιστροφή (inversion): Έστω μία ακολουθία . Αν  και , τότε λέμε ότι το ζεύγος  είναι μία αντιστροφή. Για παράδειγμα η ακολουθία  έχει τρεις αντιστροφές, τις , , .
 Ευστάθεια (stability): Ένας αλγόριθμος ταξινόμησης λέγεται ότι είναι ευσταθής (stable), αν τα στοιχεία με ίσες τιμές διατηρούν τη σειρά που είχαν στην αρχική ακολουθία. Φυσικά έχει νόημα να μιλάμε για ευστάθεια μόνο όταν τα στοιχεία φέρουν επιπλέον πληροφορία που δε λαμβάνει μέρος στην ταξινόμηση όπως για παράδειγμα όταν ταξινομούνται ζεύγη της μορφής (κλειδί , δεδομένα) και η ταξινόμηση γίνεται με βάση το κλειδί.
 Προσαρμοστικότητα (adaptability): Προσαρμοστικός (adaptive) είναι ένας αλγόριθμος ταξινόμησης όταν ταξινομεί πιο γρήγορα δεδομένα τα οποία είναι μερικώς ταξινομημένα απ' ό,τι όταν αυτά έχουν τυχαία σειρά. Παράδειγμα ενός προσαρμοστικού αλγορίθμου είναι η ταξινόμηση με εισαγωγή, ενώ ενός μη προσαρμοστικού η ταξινόμηση με συγχώνευση.
 Επιτόπου (in-place) εκτέλεση: Στην πιο αυστηρή του μορφή, ένας αλγόριθμος εκτελείται επιτόπου όταν χρησιμοποιεί σταθερό μέγεθος επιπλέον μνήμης, δηλαδή ανήκει στην κλάση DSPACE(1). Κάτι τέτοιο όμως είναι αρκετά δεσμευτικό καθώς η κλάση DSPACE(1) ισοδυναμεί με τις κανονικές γλώσσεςMaciej Liśkiewicz and Rüdiger Reischuk. The Complexity World below Logarithmic Space. Structure in Complexity Theory Conference, pp. 64-78. 1994. Online: p. 3, Theorem 2. και επίσης θεωρητικά για να αποθηκευτεί σε μία μεταβλητή το μέγεθος ενός πίνακα, απαιτείται  μνήμη. Γι' αυτό το λόγο θεωρούμε ότι οι μεταβλητές έχουν σταθερό μέγεθος και ότι ένας αλγόριθμος μπορεί να χρησιμοποιεί  μνήμη, έτσι ώστε να συμπεριλαμβάνονται αλγόριθμοι όπως η γρήγορη ταξινόμηση στους αλγορίθμους που εκτελούνται επιτόπου.

 Κάτω φράγμα ταξινόμησης 
Για όλους τους αλγόριθμους που βασίζονται σε συγκρίσεις υπάρχει ένα κάτω φράγμα για το χρόνο εκτέλεσης στη χειρότερη περίπτωση. Συγκεκριμένα για κάθε συγκριτικό αλγόριθμο που δεν χρησιμοποιεί τυχαιότητα υπάρχει ένα στιγμιότυπο εισόδου για το οποίο ο αλγόριθμος εκτελεί  συγκρίσεις.

 Απόδειξη 
Έστω  το σύνολο όλων των πιθανών εισόδων. Αρχικά το  ισούται με όλες τις δυνατές μεταθέσεις της εισόδου, δηλαδή   . Μπορούμε να σκεφτούμε μία σύγκριση ως μία διαδικασία που σπάει το  σε δύο σύνολα, σε αυτό που η απάντηση στη σύγκριση είναι ΝΑΙ και σε αυτό που η απάντηση είναι ΌΧΙ. Τότε κάθε σύγκριση σπάσει το  σε δύο υποσύνολα με το μεγαλύτερο να έχει μέγεθος τουλάχιστον . Αφού αρχικά το  έχει μέγεθος  και επειδή ο αλγόριθμος,για να γνωρίζει την απάντηση, πρέπει να μειώσει το  σε , οφήλει να εκτελέσει τουλάχιστον  συγκρίσεις. Όμως τότε:

 Κατάλογος συγκριτικών αλγόριθμων ταξινόμησης 
+ Συγκριτικοί αλγόριθμοι ταξινόμησης  Αλγόριθμος  Καλύτερη περίπτωση  Μέση περίπτωση  Χειρότερη περίπτωση  Μνήμη  Ευσταθής  Μέθοδος  Σημειώσεις Γρήγορη ταξινόμηση  (Quicksort) ,παραλλαγή του σε    Στη μέση περίπτωση  Συνήθως όταν εκτελείται επιτόπου δεν είναι ευσταθής, αν και υπάρχουν ευσταθείς υλοποιήσεις. Διαμέριση Η γρήγορη ταξινόμηση γίνεται συνήθως επιτόπου με μέγεθος στοίβας . Ταξινόμηση με συγχώνευση  (Merge sort)    Δες από κάτω για έναν υβριδικό με  μνήμη. Ναι Συγχώνευση Αρκετά παραλληλοποιήσιμος  (έως και  χρησιμοποιώντας τον αλγόριθμο των τριών Ούγγρων ή, πιο πρακτικά, με τον παράλληλο αλγόριθμο ταξινόμησης του Cole) για την επεξεργασία μεγάλου πλήθους δεδομένων. Ταξινόμηση με  επιτόπου συγχώνευση  (In-place merge sort) — —  Δες από κάτω για έναν υβριδικό που τρέχει σε   Ναι Συγχώνευση Μπορεί να είναι ευσταθής με χρήση ευσταθούς επιτόπου συγχώνευσης. Block sort     Ναι Εισαγωγή & Συγχώνευση Κάνει επιτόπου συγχώνευση με κομμάτια (blocks) σε O(n)  και υλοποιείται από κάτω προς τα πάνω. Tαξινόμηση με σωρό  (Heapsort) Αν όλα τα στοιχεία είναι διακριτά,     Όχι Επιλογή Ταξινόμηση φυσαλίδας  (Bubble sort)     Ναι  Ανταλλαγή Απλός στην υλοποίηση. Ταξινόμηση με επιλογή  (Selection sort)     Όχι Επιλογή Ευσταθής όταν χρησιμοποιείται O(n) επιπλέον μνήμη ή όταν χρησιμοποιούνται συνδεδεμένες λίστες. Ταξινόμηση με εισαγωγή  (Insertion sort)     Ναι Εισαγωγή  για ακολουθίες με d αντιστροφές (δηλαδή ζεύγη στοιχείων που είναι αντίστροφα ταξινομημένα). Shell sort     Όχι Εισαγωγή Απλός στην υλοποίηση, δεν χρησιμοποιεί αναδρομή, σχετικά γρήγορος και χρησιμοποιείται όταν δεν υπάρχει αρκετή διαθέσιμη μνήμη,για παράδειγμα στα ενσωματωμένα συστήματα.  Υπάρχει ακολουθία διαστημάτων με χειρότερη περίπτωση O(n (log n)²), αλλά τότε η καλύτερη περίπτωση υπερβαίνει το  O(n log n). Introsort     Όχι Διαμέριση & Επιλογή Χρησιμοποιεί quicksort και κάνει εναλλαγή σε ταξινόμηση με σωρό όταν το βάθος της αναδρομής γίνει μεγάλο. Χρησιμοποιείται σε πολλές υλοποιήσεις της STL. Timsort     Ναι Εισαγωγή & Διαμέριση Βασίζεται στην ταξινόμηση με συγχώνευση και στην ταξινόμηση με εισαγωγή και λαμβάνει υπόψη ήδη ταξινομημένες υποακολουθίες. Χρησιμοποιείται από την Python, Java, το Android και το GNU Octave. Cubesort     Ναι Εισαγωγή Κάνει n συγκρίσεις όταν τα δεδομένα είναι ήδη ή αντιστρόφως ταξινομημένα. Binary tree sort     Ναι Εισαγωγή Cycle sort     Όχι Εισαγωγή Εκτελείται επιτόπου με θεωρητικά βέλτιστο αριθμό εγγραφών. Library sort     Ναι Εισαγωγή Patience sorting  —   Όχι Εισαγωγή & Επιλογή Βρίσκει όλες τις μέγιστες αυξανόμενες υποακολουθίες σε . Smoothsort     Ναι Επιλογή Προσαρμοστικός, παραλλαγή της ταξινόμησης με σωρό που βασίζεται στην ακολουθία Leonardo αντί του δυαδικού σωρού. Tournament sort     Όχι Επιλογή Παραλλαγή της ταξινόμησης με σωρό. Cocktail sort     Ναι Ανταλλαγή Παραλλαγή της ταξινόμησης φυσαλίδας η οποία κάνει περάσματα και από τις δύο κατευθύνσεις. Comb sort     Όχι Ανταλλαγή Παραλλαγή της ταξινόμησης φυσαλίδας η οποία είναι γρηγορότερη στην πράξη. Gnome sort     Ναι Ανταλλαγή Παρόμοιος με την ταξινόμηση με εισαγωγή. Δεν περιέχει φωλιασμένες επαναλήψεις.

 Δείτε επίσης 
 Αλγόριθμος αναζήτησης
 Τοπολογική ταξινόμηση

 Παραπομπές 

 Εξωτερικοί σύνδεσμοι 
 A libc qsort() shootout of sorts
 Sequential and parallel sorting algorithms 
 15 αλγόριθμοι ταξινόμησης σε 6 λεπτά (video)