Χρήστης:Botaki/πρόχειρο

Αφαιρέθηκαν

Strand sort
Unshuffle sort
Franceschini's method

Μάλλον θα βγει η Μέθοδος.

Βασικές έννοιες[Επεξεργασία | επεξεργασία κώδικα]

Εσωτερική (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)$ .^[1]
Ευστάθεια (stability): Ένας αλγόριθμος ταξινόμησης λέγεται ότι είναι ευσταθής (stable), αν τα στοιχεία με ίσες τιμές διατηρούν τη σειρά που είχαν στην αρχική ακολουθία. Φυσικά έχει νόημα να μιλάμε για ευστάθεια μόνο όταν τα στοιχεία φέρουν επιπλέον πληροφορία που δε λαμβάνει μέρος στην ταξινόμηση όπως για παράδειγμα όταν ταξινομούνται ζεύγη της μορφής (κλειδί , δεδομένα) και η ταξινόμηση γίνεται με βάση το κλειδί.
Προσαρμοστικότητα (adaptability): Προσαρμοστικός (adaptive) είναι ένας αλγόριθμος ταξινόμησης όταν ταξινομεί πιο γρήγορα δεδομένα τα οποία είναι μερικώς ταξινομημένα απ' ό,τι όταν αυτά έχουν τυχαία σειρά.^[2] Παράδειγμα ενός προσαρμοστικού αλγορίθμου είναι η ταξινόμηση με εισαγωγή, ενώ ενός μη προσαρμοστικού η ταξινόμηση με συγχώνευση.
Επιτόπου (in-place) εκτέλεση: Στην πιο αυστηρή του μορφή, ένας αλγόριθμος εκτελείται επιτόπου όταν χρησιμοποιεί σταθερό μέγεθος επιπλέον μνήμης, δηλαδή ανήκει στην κλάση DSPACE(1). Κάτι τέτοιο όμως είναι αρκετά δεσμευτικό καθώς η κλάση DSPACE(1) ισοδυναμεί με τις κανονικές γλώσσες, ενώ θεωρητικά για να αποθηκευτεί σε μία μεταβλητή το μέγεθος του πίνακα, απαιτείται $\Theta (\log n)$ μνήμη. Γι' αυτό το λόγο θεωρούμε ότι οι μεταβλητές έχουν σταθερό μέγεθος και ότι ένας αλγόριθμος μπορεί να χρησιμοποιεί $\mathrm {O} (\log n)$ μνήμη, έτσι ώστε να συμπεριλαμβάνονται αλγόριθμοι όπως η γρήγορη ταξινόμηση στους αλγορίθμους που εκτελούνται επιτόπου.

Κατάλογος συγκριτικών αλγόριθμων ταξινόμησης[Επεξεργασία | επεξεργασία κώδικα]

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