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

• Εσωτερική (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)}$

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

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