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

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

Πιο συγκεκριμένα ένας αλγόριθμος ταξινόμησης είναι ένας αλγόριθμος που δοσμένης μίας ακολουθίας εισόδου (a_1,a_2,..,a_n) και μίας συνάρτησης δίαταξης f, παράγει μία ακολουθία εξόδου (a'_1,a'_2,..,a'_n) τέτοια ώστε
:
# f(a'_1) \le f(a'_2) \le ... \le f(a'_n)
# Η ακολουθία (a'_n) αποτελεί μετάθεση της (a_n)

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

## Βασικές έννοιες
* *Εσωτερική* (internal) λέγεται η ταξινόμηση η οποία γίνεται εξ ολοκλήρου στην κύρια μνήμη.
* *Εξωτερική* (external) λέγεται η ταξινόμηση που γίνεται στη δευτερεύουσα μνήμη όπως για παράδειγμα στον σκληρό δίσκο. 
* *Αντιστροφή* (inversion): Έστω μία ακολουθία (a_1,a_2, ... , a_n). Αν i  και a_i > a_j, τότε λέμε ότι το ζεύγος (a_i,a_j) είναι μία αντιστροφή. Για παράδειγμα η ακολουθία (3,1,4,2) έχει τρεις αντιστροφές, τις (3,1), (3,2), (4,2).
* *Ευστάθεια* (stability): Ένας αλγόριθμος ταξινόμησης λέγεται ότι είναι *ευσταθής* (stable), αν τα στοιχεία με ίσες τιμές διατηρούν τη σειρά που είχαν στην αρχική ακολουθία. Φυσικά έχει νόημα να μιλάμε για ευστάθεια μόνο όταν τα στοιχεία φέρουν επιπλέον πληροφορία που δε λαμβάνει μέρος στην ταξινόμηση όπως για παράδειγμα όταν ταξινομούνται ζεύγη της μορφής (κλειδί , δεδομένα) και η ταξινόμηση γίνεται με βάση το κλειδί.
* *Προσαρμοστικότητα* (adaptability): *Προσαρμοστικός* (adaptive) είναι ένας αλγόριθμος ταξινόμησης όταν ταξινομεί πιο γρήγορα δεδομένα τα οποία είναι μερικώς ταξινομημένα απ' ό,τι όταν αυτά έχουν τυχαία σειρά. Παράδειγμα ενός προσαρμοστικού αλγορίθμου είναι η ταξινόμηση με εισαγωγή, ενώ ενός μη προσαρμοστικού η ταξινόμηση με συγχώνευση.
* *Επιτόπου* (in-place) εκτέλεση: Στην πιο αυστηρή του μορφή, ένας αλγόριθμος εκτελείται επιτόπου όταν χρησιμοποιεί σταθερό μέγεθος επιπλέον μνήμης, δηλαδή ανήκει στην κλάση DSPACE(1). Κάτι τέτοιο όμως είναι αρκετά δεσμευτικό καθώς η κλάση DSPACE(1) ισοδυναμεί με τις κανονικές γλώσσες και επίσης θεωρητικά για να αποθηκευτεί σε μία μεταβλητή το μέγεθος ενός πίνακα, απαιτείται \Omega (\log n) μνήμη. Γι' αυτό το λόγο θεωρούμε ότι οι μεταβλητές έχουν σταθερό μέγεθος και ότι ένας αλγόριθμος μπορεί να χρησιμοποιεί \Omicron (\log n) μνήμη, έτσι ώστε να συμπεριλαμβάνονται αλγόριθμοι όπως η γρήγορη ταξινόμηση στους αλγορίθμους που εκτελούνται επιτόπου.

## Κάτω φράγμα ταξινόμησης
Για όλους τους αλγόριθμους που βασίζονται σε συγκρίσεις υπάρχει ένα κάτω φράγμα για το χρόνο εκτέλεσης στη χειρότερη περίπτωση. Συγκεκριμένα για κάθε συγκριτικό αλγόριθμο που δεν χρησιμοποιεί τυχαιότητα υπάρχει ένα στιγμιότυπο εισόδου για το οποίο ο αλγόριθμος εκτελεί \Omega(n \log n) συγκρίσεις.

### Απόδειξη
Έστω 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) \ge \frac{n}{2}\log_2(\frac{n}{2}) = \Omega(n \log n) 

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

## Δείτε επίσης
* Αλγόριθμος αναζήτησης
* Τοπολογική ταξινόμηση

## Παραπομπές


## Εξωτερικοί σύνδεσμοι
* A libc qsort() shootout of sorts
* Sequential and parallel sorting algorithms 
* 15 αλγόριθμοι ταξινόμησης σε 6 λεπτά (video)