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

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

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

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

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

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

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

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

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

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

Απόδειξη

Έστω $S$ το σύνολο όλων των πιθανών εισόδων. Αρχικά το $| S |$ ισούται με όλες τις δυνατές μεταθέσεις της εισόδου, δηλαδή $n!$ . Μπορούμε να σκεφτούμε μία σύγκριση ως μία διαδικασία που σπάει το $S$ σε δύο σύνολα, σε αυτό που η απάντηση στη σύγκριση είναι ΝΑΙ και σε αυτό που η απάντηση είναι ΌΧΙ. Τότε κάθε σύγκριση σπάσει το $S$ σε δύο υποσύνολα με το μεγαλύτερο να έχει μέγεθος τουλάχιστον $| S | / 2$ . Αφού αρχικά το $S$ έχει μέγεθος $n!$ και επειδή ο αλγόριθμος,για να γνωρίζει την απάντηση, πρέπει να μειώσει το $| S |$ σε $1$ , οφήλει να εκτελέσει τουλάχιστον $\log_{2} (n!)$ συγκρίσεις. Όμως τότε: $\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}) = Ω (n \log n)$

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

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

Δείτε επίσης

Παραπομπές

↑ Πρότυπο:Cite book
↑ Πρότυπο:Cite book
↑ Πρότυπο:Cite journal Πρότυπο:Dead link
↑ 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.
↑ Πρότυπο:Cite web
↑ Πρότυπο:Cite book
↑ Πρότυπο:Cite journal
↑ Πρότυπο:Cite conference
↑ Πρότυπο:Cite journal
↑ Πρότυπο:Cite conference

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

[kallipos-1] Πρότυπο:Cite book

[Knuth-2] Πρότυπο:Cite book

[3] Πρότυπο:Cite journal Πρότυπο:Dead link

[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.

[fotakis-5] Πρότυπο:Cite web

[6] Πρότυπο:Cite book

[sedgewickQsortPaper-7] Πρότυπο:Cite journal

[8] Πρότυπο:Cite conference

[9] Πρότυπο:Cite journal

[10] Πρότυπο:Cite conference

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

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

Περιεχόμενα

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

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

Απόδειξη

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

Δείτε επίσης

Παραπομπές

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

Μενού πλοήγησης

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

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

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

Απόδειξη

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

Δείτε επίσης

Παραπομπές

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

Μενού πλοήγησης

Αναζήτηση