3.7 Ταξινόμηση

Η τακτοποίηση των κόμβων μίας δομής με μία ιδιαίτερη σειρά είναι μία πολύ σημαντική λειτουργία που ονομάζεται ταξινόμηση (sorting) ή διάταξη (ordering). Συνήθως η σειρά αυτή είναι η αύξουσα τάξη (ascending sequence) της τιμής των μεγεθών προς ταξινόμηση. Από το προηγούμενο παράδειγμα έγινε σαφές ότι σκοπός της ταξινόμησης είναι να διευκολυνθεί στη συνέχεια η αναζήτηση των στοιχείων του ταξινομημένου πίνακα. Η χρησιμότητα της ταξινόμησης αποδεικνύεται στην πράξη σε αναρίθμητες περιπτώσεις αναζήτησης αριθμητικών ή αλφαβητικών δεδομένων, όπως σε βιβλιοθηκονομικά συστήματα, λεξικά, τηλεφωνικούς καταλόγους, καταλόγους φόρου εισοδήματος και γενικά παντού όπου γίνεται αναζήτηση αποθηκευμένων αντικειμένων. Στη συνέχεια δίνεται ένας τυπικός ορισμός της ταξινόμησης.

Ορισμός. Δοθέντων των στοιχείων ak1,ak2,…,akn η ταξινόμηση συνίσταται στη μετάθεση (permutation) της θέσης των στοιχείων, ώστε να τοποθετηθούν σε μία σειρά ak1,ak2,…,akn έτσι ώστε, δοθείσης μίας συνάρτησης διάταξης (ordering function), f, να ισχύει: f(ak1)[pic]f(ak2)[pic]…[pic]f(akn)

Αξίζει να σημειωθεί ότι η προηγούμενη συνάρτηση διάταξης μπορεί να τροποποιηθεί, ώστε να καλύπτει και την περίπτωση που η ταξινόμηση γίνεται με φθίνουσα τάξη (descending sequence) μεγέθους.