Ταξινόμηση

Εισαγωγή

Οι αλγόριθμοι ταξινόμησης (sorting algorithms) θέτουν τα στοιχεία μιας δομής δεδομένων σε σειρά σύμφωνα με μια ορισμένη σχέση διάταξης.
Αν τα στοιχεία είναι οργανωμένα σε εγγραφές (records) και κάθε μια από αυτές απαρτίζεται από πεδία (fields) τότε το πεδίο με βάση το οποίο γίνεται η ταξινόμηση ονομάζεται κλειδί (key) της ταξινόμησης.
Το κόστος μιας ταξινόμησης εκφράζεται ανάλογα με τον αριθμό συγκρίσεων και μετακινήσεων που απαιτούνται κατ' ελάχιστο, μέγιστο και κατά μέσο όρο.
Συχνά για να αποφευχθεί το κόστος των μετακινήσεων αντί για τα στοιχεία, ταξινομήται ένας πίνακας με δείκτες στα αντίστοιχα στοιχεία.

Στη ταξινόμηση με παρεμβολή (insertion sort) τα στοιχεία χωρίζονται σε:
- αυτά τα οποία έχουν ταξινομηθεί,
- αυτό τα οποία θα ταξινομηθεί, και
- αυτά τα οποία δεν έχουν ταξινομηθεί.
Σε κάθε βήμα το στοιχείο που πρέπει να ταξινομηθεί εισάγεται στη σωστή θέση αυτών που έχουν ταξινομηθεί.
Για την εύρεση του σημείου εισαγωγής μπορεί να χρησιμοποιηθεί και ο αλγόριθμος της δυαδικής αναζήτησης.
Οι συγκρίσεις που απαιτούνται είνα n-1 ... n*log(n)-exp(n-1) ... (n*n+n)/2-1
Οι μετακινήσεις που απαιτούνται είναι n ... 1/4(n*n+n+2) ... (n*n+n)/2

Στη ταξινόμηση με επιλογή (selection sort) τα στοιχεία χωρίζονται σε:
- αυτά τα οποία έχουν ταξινομηθεί,
- αυτά τα οποία δεν έχουν ταξινομηθεί.
Σε κάθε βήμα επιλέγεται το ελάχιστο στοιχείο από αυτά τα οποία δεν έχουν ταξινομηθεί και εισάγεται στο τέλος των στοιχείων που έχουν ταξινομηθεί.
Οι συγκρίσεις που απαιτούνται είνα (n*n-n)/2
Οι μετακινήσεις που απαιτούνται είναι (n-1)/3 ... n*n/4 + (n-1)/3

Στη ταξινόμηση με αντιμετάθεση (exchange sort) τα στοιχεία ταξινομούνται με διαδοχική αντιμετάθεση ζευγών που δεν ακολουθούν τη διάταξη της ταξινόμησης.
Ο αλγόριθμος μπορεί να βελιτωθεί εναλλάσσοντας σε κάθε πέρασμα τη φορά του ελέγχου.
Στην πρώτη περίπτωση ονομάζεται bubble sort (ταξινόμηση φυσαλίδας), στη δεύτερη shake sort.

Στην ταξινόμηση με διαμερισμό (partition exchange sort) (ή γρήγορη ταξινόμηση (quick sort)) επιλέγεται ένα στοιχείο του πίνακα και τα υπόλοιπα στοιχεία μοιράζονται σε δύο υποπίνακες ανάλογα με τη σχέση τους με το στοιχείο αυτό.
Στη συνέχεια ο αλγόριθμος καλείται αναδρομικά για τους δύο υποπίνακες.
Οι συγκρίσεις που απαιτούνται είναι n
Οι μετακινήσεις που απαιτούνται είναι n*log(n)/6

Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 119-132 Εκδόσεις Νέων Τεχνολογιών, 1993.
Donald E. Knuth. The Art of Computer Programming, volume 3 / Searching and Sorting. Addison-Wesley, second edition, 1973.
Niklaus Wirth. Algorithms + Datastructures = Programs. p. 73-134. Prentice-Hall, 1976.
Sarwar, S. Mansoor, Sarwar, Syed Aqeel, and Brandeburg, Jesse. Engineering Quicksort. Computer Languages, 22(1), 1996.