From Wikipedia, the free encyclopedia
Στην επιστήμη των υπολογιστών ο αλγόριθμος ταξινόμησης είναι ένας αλγόριθμος που μεταθέτει τα στοιχεία μίας ακολουθίας έτσι ώστε να έχουν μία συγκεκριμένη σειρά. Παραδείγματα τέτοιων σειρών αποτελούν η αριθμητική και η αλφαβητική.
Πιο συγκεκριμένα ένας αλγόριθμος ταξινόμησης είναι ένας αλγόριθμος που δοσμένης μίας ακολουθίας εισόδου και μίας συνάρτησης δίαταξης , παράγει μία ακολουθία εξόδου τέτοια ώστε [1]:
Η συνάρτηση είναι αυτή που καθορίζει τη σειρά ταξινόμησης. Έτσι επιλέγοντας η σειρά ταξινόμησης είναι η φθίνουσα.
Για όλους τους αλγόριθμους που βασίζονται σε συγκρίσεις υπάρχει ένα κάτω φράγμα για το χρόνο εκτέλεσης στη χειρότερη περίπτωση. Συγκεκριμένα για κάθε συγκριτικό αλγόριθμο που δεν χρησιμοποιεί τυχαιότητα υπάρχει ένα στιγμιότυπο εισόδου για το οποίο ο αλγόριθμος εκτελεί συγκρίσεις.[5]
Έστω το σύνολο όλων των πιθανών εισόδων. Αρχικά το ισούται με όλες τις δυνατές μεταθέσεις της εισόδου, δηλαδή . Μπορούμε να σκεφτούμε μία σύγκριση ως μία διαδικασία που σπάει το σε δύο σύνολα, σε αυτό που η απάντηση στη σύγκριση είναι ΝΑΙ και σε αυτό που η απάντηση είναι ΌΧΙ. Τότε κάθε σύγκριση σπάσει το σε δύο υποσύνολα με το μεγαλύτερο να έχει μέγεθος τουλάχιστον . Αφού αρχικά το έχει μέγεθος και επειδή ο αλγόριθμος,για να γνωρίζει την απάντηση, πρέπει να μειώσει το σε , οφήλει να εκτελέσει τουλάχιστον συγκρίσεις. Όμως τότε:
Αλγόριθμος | Καλύτερη περίπτωση | Μέση περίπτωση | Χειρότερη περίπτωση | Μνήμη | Ευσταθής | Μέθοδος | Σημειώσεις |
---|---|---|---|---|---|---|---|
Γρήγορη ταξινόμηση (Quicksort) |
, παραλλαγή του σε |
Στη μέση περίπτωση , στη χειρότερη . Η παραλλαγή του Sedgewick έχει στη χειρότερη περίπτωση .[6] | Συνήθως όταν εκτελείται επιτόπου δεν είναι ευσταθής, αν και υπάρχουν ευσταθείς υλοποιήσεις. | Διαμέριση | Η γρήγορη ταξινόμηση γίνεται συνήθως επιτόπου με μέγεθος στοίβας O(log n).[7][8] | ||
Ταξινόμηση με συγχώνευση (Merge sort) |
Δες από κάτω για έναν υβριδικό με μνήμη. |
Ναι | Συγχώνευση | Αρκετά παραλληλοποιήσιμος (έως και O(log n) χρησιμοποιώντας τον αλγόριθμο των τριών Ούγγρων[9] ή, πιο πρακτικά, με τον παράλληλο αλγόριθμο ταξινόμησης του Cole) για την επεξεργασία μεγάλου πλήθους δεδομένων. | |||
Ταξινόμηση με επιτόπου συγχώνευση (In-place merge sort) |
— | — | Δες από κάτω για έναν υβριδικό που τρέχει σε |
Ναι | Συγχώνευση | Μπορεί να είναι ευσταθής με χρήση ευσταθούς επιτόπου συγχώνευσης.[10] | |
Block sort | Ναι | Εισαγωγή & Συγχώνευση | Κάνει επιτόπου συγχώνευση με κομμάτια (blocks) σε O(n) [11] και υλοποιείται από κάτω προς τα πάνω. | ||||
Tαξινόμηση με σωρό (Heapsort) |
Αν όλα τα στοιχεία είναι διακριτά, |
Όχι | Επιλογή | ||||
Ταξινόμηση φυσαλίδας (Bubble sort) |
Ναι | Ανταλλαγή | Απλός στην υλοποίηση. | ||||
Ταξινόμηση με επιλογή (Selection sort) |
Όχι | Επιλογή | Ευσταθής όταν χρησιμοποιείται O(n) επιπλέον μνήμη ή όταν χρησιμοποιούνται συνδεδεμένες λίστες. | ||||
Ταξινόμηση με εισαγωγή (Insertion sort) |
Ναι | Εισαγωγή | O(n + d) για ακολουθίες με 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 | — | Όχι | Εισαγωγή & Επιλογή | Βρίσκει όλες τις μέγιστες αυξανόμενες υποακολουθίες σε O(n log n). | |||
Smoothsort | Ναι | Επιλογή | Προσαρμοστικός, παραλλαγή της ταξινόμησης με σωρό που βασίζεται στην ακολουθία Leonardo αντί του δυαδικού σωρού. | ||||
Tournament sort | [12] | Όχι | Επιλογή | Παραλλαγή της ταξινόμησης με σωρό. | |||
Cocktail sort | Ναι | Ανταλλαγή | Παραλλαγή της ταξινόμησης φυσαλίδας η οποία κάνει περάσματα και από τις δύο κατευθύνσεις. | ||||
Comb sort | Όχι | Ανταλλαγή | Παραλλαγή της ταξινόμησης φυσαλίδας η οποία είναι γρηγορότερη στην πράξη. | ||||
Gnome sort | Ναι | Ανταλλαγή | Παρόμοιος με την ταξινόμηση με εισαγωγή. Δεν περιέχει φωλιασμένες επαναλήψεις. | ||||
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.