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

Αναπαράσταση ταξινόμησης πίνακα με τυχαίες τιμές με χρήση του αλγορίθμου γρήγορης ταξινόμησης (Quicksort)

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

Πιο συγκεκριμένα ένας αλγόριθμος ταξινόμησης είναι ένας αλγόριθμος που δοσμένης μίας ακολουθίας εισόδου ${\displaystyle (a_{1},a_{2},..,a_{n})}$ και μίας συνάρτησης δίαταξης ${\displaystyle f}$, παράγει μία ακολουθία εξόδου ${\displaystyle (a'_{1},a'_{2},..,a'_{n})}$ τέτοια ώστε ^[1]:

1. ${\displaystyle f(a'_{1})\leq f(a'_{2})\leq ...\leq f(a'_{n})}$
2. Η ακολουθία ${\displaystyle (a'_{n})}$ αποτελεί μετάθεση της ${\displaystyle (a_{n})}$

Η συνάρτηση ${\displaystyle f}$ είναι αυτή που καθορίζει τη σειρά ταξινόμησης. Έτσι επιλέγοντας ${\displaystyle f(x)=-x}$ η σειρά ταξινόμησης είναι η φθίνουσα.

Βασικές έννοιες

• Εσωτερική (internal) λέγεται η ταξινόμηση η οποία γίνεται εξ ολοκλήρου στην κύρια μνήμη.
• Εξωτερική (external) λέγεται η ταξινόμηση που γίνεται στη δευτερεύουσα μνήμη όπως για παράδειγμα στον σκληρό δίσκο.
• Αντιστροφή (inversion): Έστω μία ακολουθία ${\displaystyle (a_{1},a_{2},...,a_{n})}$. Αν ${\displaystyle i<j}$ και ${\displaystyle a_{i}>a_{j}}$, τότε λέμε ότι το ζεύγος ${\displaystyle (a_{i},a_{j})}$ είναι μία αντιστροφή. Για παράδειγμα η ακολουθία ${\displaystyle (3,1,4,2)}$ έχει τρεις αντιστροφές, τις ${\displaystyle (3,1)}$, ${\displaystyle (3,2)}$, ${\displaystyle (4,2)}$.^[2]
• Ευστάθεια (stability): Ένας αλγόριθμος ταξινόμησης λέγεται ότι είναι ευσταθής (stable), αν τα στοιχεία με ίσες τιμές διατηρούν τη σειρά που είχαν στην αρχική ακολουθία. Φυσικά έχει νόημα να μιλάμε για ευστάθεια μόνο όταν τα στοιχεία φέρουν επιπλέον πληροφορία που δε λαμβάνει μέρος στην ταξινόμηση όπως για παράδειγμα όταν ταξινομούνται ζεύγη της μορφής (κλειδί , δεδομένα) και η ταξινόμηση γίνεται με βάση το κλειδί.
• Προσαρμοστικότητα (adaptability): Προσαρμοστικός (adaptive) είναι ένας αλγόριθμος ταξινόμησης όταν ταξινομεί πιο γρήγορα δεδομένα τα οποία είναι μερικώς ταξινομημένα απ' ό,τι όταν αυτά έχουν τυχαία σειρά.^[3] Παράδειγμα ενός προσαρμοστικού αλγορίθμου είναι η ταξινόμηση με εισαγωγή, ενώ ενός μη προσαρμοστικού η ταξινόμηση με συγχώνευση.
• Επιτόπου (in-place) εκτέλεση: Στην πιο αυστηρή του μορφή, ένας αλγόριθμος εκτελείται επιτόπου όταν χρησιμοποιεί σταθερό μέγεθος επιπλέον μνήμης, δηλαδή ανήκει στην κλάση DSPACE(1). Κάτι τέτοιο όμως είναι αρκετά δεσμευτικό καθώς η κλάση DSPACE(1) ισοδυναμεί με τις κανονικές γλώσσες^[4] και επίσης θεωρητικά για να αποθηκευτεί σε μία μεταβλητή το μέγεθος ενός πίνακα, απαιτείται ${\displaystyle \Omega (\log n)}$ μνήμη. Γι' αυτό το λόγο θεωρούμε ότι οι μεταβλητές έχουν σταθερό μέγεθος και ότι ένας αλγόριθμος μπορεί να χρησιμοποιεί ${\displaystyle \mathrm {O} (\log n)}$ μνήμη, έτσι ώστε να συμπεριλαμβάνονται αλγόριθμοι όπως η γρήγορη ταξινόμηση στους αλγορίθμους που εκτελούνται επιτόπου.

Κάτω φράγμα ταξινόμησης

Για όλους τους αλγόριθμους που βασίζονται σε συγκρίσεις υπάρχει ένα κάτω φράγμα για το χρόνο εκτέλεσης στη χειρότερη περίπτωση. Συγκεκριμένα για κάθε συγκριτικό αλγόριθμο που δεν χρησιμοποιεί τυχαιότητα υπάρχει ένα στιγμιότυπο εισόδου για το οποίο ο αλγόριθμος εκτελεί ${\displaystyle \Omega (n\log n)}$ συγκρίσεις.^[5]

Απόδειξη

Έστω ${\displaystyle S}$ το σύνολο όλων των πιθανών εισόδων. Αρχικά το ${\displaystyle |S|}$ ισούται με όλες τις δυνατές μεταθέσεις της εισόδου, δηλαδή ${\displaystyle n!}$ . Μπορούμε να σκεφτούμε μία σύγκριση ως μία διαδικασία που σπάει το ${\displaystyle S}$ σε δύο σύνολα, σε αυτό που η απάντηση στη σύγκριση είναι ΝΑΙ και σε αυτό που η απάντηση είναι ΌΧΙ. Τότε κάθε σύγκριση σπάσει το ${\displaystyle S}$ σε δύο υποσύνολα με το μεγαλύτερο να έχει μέγεθος τουλάχιστον ${\displaystyle |S|/2}$. Αφού αρχικά το ${\displaystyle S}$ έχει μέγεθος ${\displaystyle n!}$ και επειδή ο αλγόριθμος,για να γνωρίζει την απάντηση, πρέπει να μειώσει το ${\displaystyle |S|}$ σε ${\displaystyle 1}$, οφήλει να εκτελέσει τουλάχιστον ${\displaystyle \log _{2}(n!)}$ συγκρίσεις. Όμως τότε: ${\displaystyle \log _{2}(n!)=\log _{2}(n*(n-1)*..*2*1)=\log _{2}(n)+\log _{2}(n-1)+..+\log _{2}(1)\geq {\frac {n}{2}}\log _{2}({\frac {n}{2}})=\Omega (n\log n)}$

Κατάλογος συγκριτικών αλγόριθμων ταξινόμησης

Συγκριτικοί αλγόριθμοι ταξινόμησης

Αλγόριθμος	Καλύτερη περίπτωση	Μέση περίπτωση	Χειρότερη περίπτωση	Μνήμη	Ευσταθής	Μέθοδος	Σημειώσεις
Γρήγορη ταξινόμηση (Quicksort)	15 !${\displaystyle n\log n}$, παραλλαγή του σε 15 !${\displaystyle n}$	20 !${\displaystyle n\log n}$	25 !${\displaystyle n^{2}}$	Στη μέση περίπτωση 05 !${\displaystyle \log n}$, στη χειρότερη ${\displaystyle n}$. Η παραλλαγή του Sedgewick έχει στη χειρότερη περίπτωση ${\displaystyle \log n}$.[6]	Συνήθως όταν εκτελείται επιτόπου δεν είναι ευσταθής, αν και υπάρχουν ευσταθείς υλοποιήσεις.	Διαμέριση	Η γρήγορη ταξινόμηση γίνεται συνήθως επιτόπου με μέγεθος στοίβας O(log n).[7][8]
Ταξινόμηση με συγχώνευση (Merge sort)	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	15 !${\displaystyle n}$ Δες από κάτω για έναν υβριδικό με ${\displaystyle \mathrm {O} (1)}$ μνήμη.	Ναι	Συγχώνευση	Αρκετά παραλληλοποιήσιμος (έως και O(log n) χρησιμοποιώντας τον αλγόριθμο των τριών Ούγγρων[9] ή, πιο πρακτικά, με τον παράλληλο αλγόριθμο ταξινόμησης του Cole) για την επεξεργασία μεγάλου πλήθους δεδομένων.
Ταξινόμηση με επιτόπου συγχώνευση (In-place merge sort)	—	—	23 !${\displaystyle n\log ^{2}n}$ Δες από κάτω για έναν υβριδικό που τρέχει σε 23 !${\displaystyle n\log n}$	00 !${\displaystyle 1}$	Ναι	Συγχώνευση	Μπορεί να είναι ευσταθής με χρήση ευσταθούς επιτόπου συγχώνευσης.[10]
Block sort	15 !${\displaystyle n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	00 !${\displaystyle 1}$	Ναι	Εισαγωγή & Συγχώνευση	Κάνει επιτόπου συγχώνευση με κομμάτια (blocks) σε O(n) [11] και υλοποιείται από κάτω προς τα πάνω.
Tαξινόμηση με σωρό (Heapsort)	20 !${\displaystyle n}$ Αν όλα τα στοιχεία είναι διακριτά, 20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	00 !${\displaystyle 1}$	Όχι	Επιλογή
Ταξινόμηση φυσαλίδας (Bubble sort)	15 !${\displaystyle n}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Ναι	Ανταλλαγή	Απλός στην υλοποίηση.
Ταξινόμηση με επιλογή (Selection sort)	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Όχι	Επιλογή	Ευσταθής όταν χρησιμοποιείται O(n) επιπλέον μνήμη ή όταν χρησιμοποιούνται συνδεδεμένες λίστες.
Ταξινόμηση με εισαγωγή (Insertion sort)	15 !${\displaystyle n}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Ναι	Εισαγωγή	O(n + d) για ακολουθίες με d αντιστροφές (δηλαδή ζεύγη στοιχείων που είναι αντίστροφα ταξινομημένα).
Shell sort	20 !${\displaystyle n\log n}$	23 ! Εξαρτάται από την ακολουθία διαστημάτων.	23 ! Εξαρτάται από την ακολουθία διαστημάτων· η καλύτερη γνωστή είναι ${\displaystyle n^{4/3}}$	00 !${\displaystyle 1}$	Όχι	Εισαγωγή	Απλός στην υλοποίηση, δεν χρησιμοποιεί αναδρομή, σχετικά γρήγορος και χρησιμοποιείται όταν δεν υπάρχει αρκετή διαθέσιμη μνήμη,για παράδειγμα στα ενσωματωμένα συστήματα. Υπάρχει ακολουθία διαστημάτων με χειρότερη περίπτωση O(n (log n)²), αλλά τότε η καλύτερη περίπτωση υπερβαίνει το O(n log n).
Introsort	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	05 !${\displaystyle \log n}$	Όχι	Διαμέριση & Επιλογή	Χρησιμοποιεί quicksort και κάνει εναλλαγή σε ταξινόμηση με σωρό όταν το βάθος της αναδρομής γίνει μεγάλο. Χρησιμοποιείται σε πολλές υλοποιήσεις της STL.
Timsort	15 !${\displaystyle n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	15 !${\displaystyle n}$	Ναι	Εισαγωγή & Διαμέριση	Βασίζεται στην ταξινόμηση με συγχώνευση και στην ταξινόμηση με εισαγωγή και λαμβάνει υπόψη ήδη ταξινομημένες υποακολουθίες. Χρησιμοποιείται από την Python, Java, το Android και το GNU Octave.
Cubesort	15 !${\displaystyle n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	15 !${\displaystyle n}$	Ναι	Εισαγωγή	Κάνει n συγκρίσεις όταν τα δεδομένα είναι ήδη ή αντιστρόφως ταξινομημένα.
Binary tree sort	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$ Όταν χρησιμοποιείται ισοζυγισμένο δέντρο	15 !${\displaystyle n}$	Ναι	Εισαγωγή
Cycle sort	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Όχι	Εισαγωγή	Εκτελείται επιτόπου με θεωρητικά βέλτιστο αριθμό εγγραφών.
Library sort	15 !${\displaystyle n}$	20 !${\displaystyle n\log n}$	25 !${\displaystyle n^{2}}$	15 !${\displaystyle n}$	Ναι	Εισαγωγή
Patience sorting	15 !${\displaystyle n}$	—	20 !${\displaystyle n\log n}$	15 !${\displaystyle n}$	Όχι	Εισαγωγή & Επιλογή	Βρίσκει όλες τις μέγιστες αυξανόμενες υποακολουθίες σε O(n log n).
Smoothsort	15 !${\displaystyle n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	00 !${\displaystyle 1}$	Ναι	Επιλογή	Προσαρμοστικός, παραλλαγή της ταξινόμησης με σωρό που βασίζεται στην ακολουθία Leonardo αντί του δυαδικού σωρού.
Tournament sort	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	20 !${\displaystyle n\log n}$	15 !${\displaystyle n}$[12]	Όχι	Επιλογή	Παραλλαγή της ταξινόμησης με σωρό.
Cocktail sort	15 !${\displaystyle n}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Ναι	Ανταλλαγή	Παραλλαγή της ταξινόμησης φυσαλίδας η οποία κάνει περάσματα και από τις δύο κατευθύνσεις.
Comb sort	15 !${\displaystyle n\log n}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Όχι	Ανταλλαγή	Παραλλαγή της ταξινόμησης φυσαλίδας η οποία είναι γρηγορότερη στην πράξη.
Gnome sort	15 !${\displaystyle n}$	25 !${\displaystyle n^{2}}$	25 !${\displaystyle n^{2}}$	00 !${\displaystyle 1}$	Ναι	Ανταλλαγή	Παρόμοιος με την ταξινόμηση με εισαγωγή. Δεν περιέχει φωλιασμένες επαναλήψεις.

Δείτε επίσης

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

Παραπομπές

1. Κωνσταντίνος Τσίχλας· Ιωάννης Μανωλόπουλος· Αναστάσιος Γούναρης. «Αλγόριθμοι Ταξινόμησης». Σχεδίαση και Ανάλυση Αλγορίθμων (PDF). ISBN 978-960-603-465-7. Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 18 Μαρτίου 2020. Ανακτήθηκε στις 9 Σεπτεμβρίου 2018. 
2. Donald Knuth (1998). The Art of Computer Programming. 3: Sorting and Searching (2η έκδοση). Addison-Wesley. ISBN 0-201-89685-0. 
3. Ola Petersson; Alistair Moffat (1992). «A framework for adaptive sorting». Lecture Notes in Computer Science. Lecture Notes in Computer Science (Berlin: Springer Berlin / Heidelberg) 621: 422–433. doi:10.1007/3-540-55706-7_38. ISBN 978-3-540-55706-7. ISSN 1611-3349. http://www.springerlink.com/content/yv85w0u75777j021/. Ανακτήθηκε στις 2009-02-23. ^{[νεκρός σύνδεσμος]}
4. 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.
5. Δημήτρης Φωτάκης. «Ταξινόμηση-Aναζήτηση-Eπιλογή» (PDF). 
6. Σύμφωνα με αυτήν την παραλλαγή γίνεται αναδρομή στον μικρότερο από τους δύο υποπίνακες της διαμέρισης ενώ για το δεύτερο γίνεται επαναληπτικά αφού αποτελεί tail recursion.
7. Sedgewick, Robert (1 Σεπτεμβρίου 1998). Algorithms In C: Fundamentals, Data Structures, Sorting, Searching, Parts 1-4 (3η έκδοση). Pearson Education. ISBN 978-81-317-1291-7. Ανακτήθηκε στις 27 Νοεμβρίου 2012. 
8. Robert Sedgewick (1978). «Implementing Quicksort programs». Communications of the ACM 21 (10): 847–857. doi:10.1145/359619.359631. 
9. Miklos Ajtai; János Komlós; Endre Szemerédi (1983). «An O(n log n) sorting network». Symposium on Theory of Computing '83, pp. 1–9. doi:10.1145/800061.808726. ISBN 0-89791-099-0. 
10. Huang, B. C.; Langston, M. A. (Δεκέμβριος 1992). «Fast Stable Merging and Sorting in Constant Extra Space». The Computer Journal 35 (6): 643–650. doi:10.1093/comjnl/35.6.643. http://comjnl.oxfordjournals.org/content/35/6/643.full.pdf. 
11. Kim, P. S.; Kutzner, A. (2008). «Ratio Based Stable In-Place Merging». LNCS. 4978. TAMC 2008, pp. 246–257. doi:10.1007/978-3-540-79228-4_22. ISBN 978-3-540-79227-7. 
12. http://dbs.uni-leipzig.de/skripte/ADS1/PDF4/kap4.pdf

Εξωτερικοί σύνδεσμοι

• A libc qsort() shootout of sorts
• Sequential and parallel sorting algorithms Αρχειοθετήθηκε 2012-12-13 στο Wayback Machine.
• 15 αλγόριθμοι ταξινόμησης σε 6 λεπτά (video)