Κεφάλαιο 8Αλγόριθμοι Ταξινόμησης

Αρχικά, θα εξετάσουμε τον αλγόριθμο της ταξινόμησης με εισαγωγή και θα καταλάβουμε τη συμπεριφορά του σε δύο περιπτώσεις: δίνοντας στην είσοδο τους πίνακες Α1=[1,2,3,4,5,6] και Α2=[6,5,4,3,2,1], με στοιχεία που είναι ήδη ταξινομημένα ή αντίστροφη σειρά ταξινομημένα. Παρατηρούμε ότι οι περιπτώσεις αυτές είναι ακραίες και δεν μπορούν να χαρακτηρισθούν ως η μέση περίπτωση, η περίπτωση δηλαδή όπου τα στοιχεία του πίνακα εμφανίζονται με μία τυχαία σειρά. Με την ίδια προσέγγιση θα ασχοληθούμε με την ταξινόμηση με επιλογή στο αμέσως επόμενο Κεφάλαιο 8.2. Ακολουθεί ο ψευδοκώδικας για τον αλγόριθμό μας.

     procedure insert
1.   for i <-- 2 to n do
2.      x <-- A[i];
3.      j <-- i-1;
4.      while j>0 and x<A[j] do
5.         A[j+1] <-- A[j]
6.         j <-- j-1
7.      A[j+1] <-- x

Η μέθοδος αυτή διακρίνει τον πίνακα σε δύο τμήματα: την ακολουθία πηγής (source sequence) και την ακολουθία προορισμού (destimation sequence). Δηλαδή, λαμβάνει στοιχεία από την ακολουθία πηγής και τα κατευθύνει στη σωστή θέση στην ακολουθία προορισμού. Έτσι, κάθε φορά το μέγεθος της ακολουθίας πηγής μειώνεται κατά ένα, ενώ το μέγεθος της ακολουθίας προορισμού αυξάνεται κατά ένα. Το κάθε φορά λαμβανόμενο στοιχείο είναι πρώτο της ακολουθίας πηγής (δες την εντολή 3). Το στοιχείο αυτό συγκρίνεται με τα στοιχεία της ακολουθίας προορισμού αρχίζοντας από το τέλος και συνεχίζοντας προς την αρχή μέχρι να εντοπίσει την κατάλληλη θέση. Ένα παράδειγμα του αλγορίθμου απεικονίζεται στο Σχήμα 8.1.

Πρόταση.
Η πολυπλοκότητα της ταξινόμησης με εισαγωγή για την καλύτερη, τη μέση και τη χειρότερη περίπτωση είναι Θ($n$), Θ($n^2$) και Θ($n^2$), αντιστοίχως.

Απόδειξη
Αν στην είσοδο θεωρηθεί ο πίνακας Α1, τότε η ταξινόμηση συμπεριφέρεται πολύ αποτελεσματικά και δεν εισέρχεται μέσα στο σώμα της εντολής 4. Έτσι, ουσιαστικά το κάθε φορά λαμβανόμενο στοιχείο από την ακολουθία πηγής συγκρίνεται με ένα μόνο στοιχείο (όπως προκύπτει από τη συνθήκη ελέγχου 4). Θεωρώντας αυτή τη σύγκριση ως την πράξη βαρόμετρο, καταλήγουμε ότι για ένα πίνακα μεγέθους $n$ στοιχείων, ο αντίστοιχος αριθμός συγκρίσεων είναι $n-1$. Επομένως, προκύπτει ότι στην καλύτερη περίπτωση η πολυπλοκότητα είναι γραμμική Θ($n$).

Τώρα ας θεωρήσουμε την περίπτωση όπου στην είσοδο δίνεται ο πίνακας Α2. Το κάθε φορά επιλεγόμενο στοιχείο είναι μικρότερο από τα ήδη τοποθετημένα στην ακολουθία προορισμού. Έτσι, εκτελείται ένας συγκεκριμένος αριθμός συγκρίσεων μέχρι να τοποθετηθεί το νέο στοιχείο στη σωστή θέση, δηλαδή στην πρώτη θέση της ακολουθίας προορισμού. Έτσι, η εντολή 5 εκτελείται $i$ φορές, όπου το $i$ μεταβάλλεται από 1 μέχρι $n-1$. Συνεπώς και πάλι θεωρώντας την πράξη αυτή ως βαρόμετρο, καταλήγουμε ότι για ένα πίνακα μεγέθους $n$ στοιχείων, o αντίστοιχος αριθμός συγκρίσεων είναι ${\sum }_{i=1}^{n-1}i=n(n-1)/2$. Επομένως, η πολυπλοκότητα στη χειρότερη περίπτωση είναι τετραγωνική Θ($n^2$).

Το σημαντικότερο ερώτημα προκύπτει στην περίπτωση ταξινόμησης τυχαίων δεδομένων εισόδου, δηλαδή στην περίπτωση, όπου οποιαδήποτε από τις $n!$ διατάξεις των δεδομένων εισόδου μπορεί να εμφανισθεί με ίση πιθανότητα $1/n!$. Η επίδοση αυτή μπορεί να προκύψει θεωρώντας ότι το στοιχείο που κάθε φορά λαμβάνεται από την ακολουθία πηγής θα διανύσει το μισό δρόμο μέχρι την αρχή της ακολουθίας προορισμού. Όπως προηγουμένως, και πάλι θα προκύψει ότι στη μέση αυτή περίπτωση η επίδοση περιγράφεται από μία τετραγωνική συνάρτηση, επομένως και στην περίπτωση αυτή η πολυπλοκότητα είναι Θ($n^2$). $\mathrm{\square }$

Από το Κεφάλαιο 1.5 αντιγράφουμε τον ψευδοκώδικα της ταξινόμησης με επιλογή.

     procedure select
1.   for i <-- 1 to n-1 do
2.      minj <-- i; minx <-- A[i];
3.      for j <-- i+1 to n do
4.         if A[j]<minx then
5.            minj <-- j
6.            minx <-- A[j]
7.      A[minj] <-- A[i]
8.      A[i] <-- minx

Πρόταση.
Η πολυπλοκότητα της ταξινόμησης με επιλογή είναι Θ($n^2$) σε κάθε περίπτωση.

Απόδειξη
Όπως φαίνεται στον ψευδοκώδικα, ουσιαστικά ο αλγόριθμος της ταξινόμησης με επιλογή σαρώνει τον πίνακα, ώστε να εντοπίσει το μικρότερο στοιχείο και να το τοποθετήσει στην πρώτη θέση. Στη συνέχεια, περιορίζει την αναζήτηση στα υπόλοιπα $n-1$ στοιχεία, ώστε να εντοπίσει το μικρότερο μεταξύ αυτών και να το τοποθετήσει στη δεύτερη θέση κοκ. Επομένως, εύκολα προκύπτει ότι η εντολή 4 (δηλαδή, if A[j]<minx) θα εκτελεσθεί τον ίδιο αριθμό επαναλήψεων ανεξαρτήτως του περιεχομένου του πίνακα εισόδου. Είτε, λοιπόν, στην είσοδο δοθεί ο πίνακας Α1 είτε ο Α2, το αντίστοιχο πλήθος συγκρίσεων θα είναι: ${\sum }_{i=1}^{n-1}i=n(n-1)/2$. Επομένως, σε κάθε περίπτωση η πολυπλοκότητα είναι τετραγωνική Θ($n^2$). $\mathrm{\square }$  

Από το παράδειγμα αυτό εξάγεται το συμπέρασμα ότι η ταξινόμηση με επιλογή έχει την ίδια επίδοση (δηλαδή, τετραγωνική πολυπλοκότητα) ανεξαρτήτως των δεδομένων εισόδου. Έτσι, επιβεβαιώνουμε κάτι που αναφέραμε στο Κεφάλαιο 2, δηλαδή ότι ο αλγόριθμος αυτός είναι σταθερός (robust), επειδή έχει ταυτόσημες την καλύτερη, χειρότερη και μέση περίπτωση. Αντίθετα, δεν συμβαίνει το ίδιο με τον αλγόριθμο ταξινόμησης με εισαγωγή.

Καθώς η εξέταση του πλήθους των συγκρίσεων ήταν εύκολη υπόθεση, στη συνέχεια θα εξετάσουμε τον αλγόριθμο αυτό, ώστε να προσδιορίσουμε το πλήθος των καταχωρήσεων. Καθώς υπάρχουν αρκετές καταχωρήσεις στον αλγόριθμο, επιλέγουμε ως σημαντικότερη την καταχώρηση minx <-- A[j] της εντολής 6 εντός του εσωτερικού βρόχου, παρά τις καταχωρήσεις που εκτελούνται εκτός του εσωτερικού αλλά εντός του εξωτερικού βρόχου. Εξάλλου είναι εύκολο να διαπιστωθεί ότι οι καταχωρήσεις στις εντολές minj <-- i; minx <-- A[i]; A[minj] <-- A[i] και A[i] <-- minx (εντολές 2, 7, 8) θα εκτελεσθούν συνολικά $4(n-1)$ φορές.

Πρόταση.
Η μέση τιμή του πλήθους των καταχωρήσεων κατά την ταξινόμηση με επιλογή είναι Θ($n\log n$).

Απόδειξη
Ας υποθέσουμε ότι τα στοιχεία του πίνακα είναι διακριτά και ότι κάθε μία από τις $n!$ διατάξεις είναι ισοπίθανες να συμβούν. Στην $i$-οστή επανάληψη ο αλγόριθμος αναζητά το μικρότερο μεταξύ των $n-i+1$ στοιχείων του πίνακα στα δεξιά της θέσης $i$ (συμπεριλαμβανομένης της θέσης αυτής). Έστω ότι με $R(m)$ συμβολίζουμε το πλήθος των καταχωρήσεων που απαιτούνται για την επιλογή του ελάχιστου μεταξύ των $m$ στοιχείων, οπότε για τη μέση τιμή του $R(m)$ ισχύει:

όπου $S(m)$ είναι το πλήθος των καταχωρήσεων που αθροίζονται κατά την εκτέλεση των $m!$ διαφορετικών διατάξεων των $m$ στοιχείων.

Ας θεωρήσουμε τις $(m-1)!$ περιπτώσεις, όπου το ελάχιστο στοιχείο εντοπίζεται στην τελευταία θέση του πίνακα. Στην περίπτωση αυτή το πλήθος των καταχωρήσεων είναι

καθώς ο αλγόριθμος συμπεριφέρεται σαν να υπήρχαν αρχικά $(m-1)$ μη επαναλαμβανόμενα στοιχεία, οπότε στη συνέχεια θα εκτελούνταν άλλη μία καταχώρηση για κάθε μία από τις $(m-1)!$ διαφορετικές διατάξεις. Αν εξαιρεθεί η τελευταία περίπτωση (δηλαδή, το ελάχιστο βρίσκεται στην τελευταία θέση), τότε απομένουν προς εξέταση $(m-1)(m-1)!$ περιπτώσεις. Στις περιπτώσεις αυτές το ελάχιστο στοιχείο βρίσκεται από την πρώτη μέχρι την $(m-1)$-οστή θέση, οπότε για κάθε ομάδα $(m-1)!$ διατάξεων απαιτούνται $S(m-1)$ καταχωρήσεις. Αυτό συνολικά δίνει άλλες

καταχωρήσεις. Έτσι, προκύπτει η αναδρομική εξίσωση:

με αρχική συνθήκη $S(1)=0$. Άρα, για τη μέση τιμή του $R(m)$ ισχύει:

που επιλύεται εύκολα και δίνει τη λύση:

Λαμβάνοντας υπ’όψιν το σύνολο των $n-1$ επαναλήψεων του εξωτερικού βρόχου (εντολή 1) προκύπτει ότι η μέση τιμή του πλήθους των καταχωρήσεων είναι:

Άρα, προκύπτει ότι στη μέση περίπτωση το πλήθος των καταχωρήσεων είναι της τάξης Θ($n\log n$). Ακόμη και αν προσθέταμε τις $4(n-1)$ καταχωρήσεις που εκτελούνται εκτός του εσωτερικού βρόχου, και πάλι το αποτέλεσμα δε θα άλλαζε. $\mathrm{\square }$  

Ένα τελικό σχόλιο. Μία μέθοδος ταξινόμησης λέγεται ευσταθής (stable), αν διατηρεί τη σχετική θέση πριν και μετά τη διάταξη για τα στοιχεία με την ίδια τιμή. Σε αντίθετη περίπτωση λέγεται ασταθής. Στο Σχήμα 8.2 παρουσιάζεται μία περίπτωση ευσταθούς και μία περίπτωση ασταθούς αλγορίθμου. Η ταξινόμηση με εισαγωγή είναι ευσταθής, αν και η μέθοδος αυτή έχει κακή σταθερή πολυπλοκότητα Θ($n^2$). Για την περίπτωση της γρήγορης ταξινόμησης που θα μελετήσουμε στη συνέχεια, θα παρατηρήσουμε ότι η τελευταία αυτή μέθοδος δεν είναι ευσταθής, καθώς εκτελεί περιττές μετακινήσεις ίσων κλειδιών. Παρ’ όλ’ αυτά δεν παύει να θεωρείται μία πολύ αποτελεσματική μέθοδος.

Η γρήγορη ταξινόμηση (quicksort), που αλλιώς ονομάζεται και ταξινόμηση με διαμερισμό και ανταλλαγή (partition exchange sort), θεωρείται ένας από τους top-10 αλγορίθμους ως προς την πρακτική χρησιμότητά και το ενδιαφέρον που προκάλεσε από τη θεωρητική σκοπιά. Η γρήγορη ταξινόμηση αποτελεί ένα κλασικό παράδειγμα αλγορίθμου της οικογενείας Διαίρει και Βασίλευε. Όπως δηλώνει το πρώτο όνομα του αλγορίθμου, πρόκειται για μία πολύ αποτελεσματική μέθοδο ταξινόμησης (πλην ελαχίστων εξαιρέσεων). Όπως δηλώνει το δεύτερο όνομά του, τα βασικά χαρακτηριστικά του είναι δύο: η ανταλλαγή και ο διαμερισμός. Πρώτον, δηλαδή, εκτελούνται ανταλλαγές μεταξύ των στοιχείων του πίνακα, έτσι ώστε τα στοιχεία με μικρότερες τιμές να μετακινηθούν προς τη μία πλευρά, ενώ τα στοιχεία με μεγαλύτερες τιμές να μετακινηθούν προς την άλλη πλευρά του πίνακα. Έτσι, επακολουθεί η εφαρμογή του δεύτερου χαρακτηριστικού, δηλαδή του διαμερισμού του πίνακα σε δύο μικρότερους που ταξινομούνται ανεξάρτητα μεταξύ τους. Είναι προφανές ότι στους δύο υποπίνακες επιφυλάσσεται η ίδια αντιμετώπιση: ανταλλαγή και διαμερισμός.

     procedure quicksort(left,right);
1.   if left<right then
2.      i <-- left; j <-- right+1; pivot <-- A[left];
3.      repeat
4.         repeat i <-- i+1 until A[i]>=pivot;
5.         repeat j <-- j-1 until A[j]<=pivot;
6.         if i<j then swap(A[i],A[j]);
7.      until j<=i;
8.      swap(A[left],A[j]);
9.      quicksort(left,j-1);
10.     quicksort(j+1,right)

Η προηγούμενη διαδικασία quicksort υποθέτει ότι δίνεται προς ταξινόμηση ένας πίνακας A[1..n], που περιέχει ακεραίους αριθμούς. Ο pivot είναι ένα στοιχείο του πίνακα, το οποίο παίρνει την τελική του θέση στον πίνακα, ώστε κατόπιν να γίνει ο διαμερισμός (δηλαδή, να γίνουν οι κλήσεις της partition) σε δύο υποπίνακες με μικρότερα και μεγαλύτερα στοιχεία από τον pivot αντίστοιχα. Η επιλογή του pivot μπορεί να γίνει κατά πολλούς τρόπους. Στο σημείο αυτό δεχόμαστε ότι ως pivot λαμβάνεται το πρώτο στοιχείο του πίνακα. Έτσι, ο πίνακας σαρώνεται από τα αριστερά προς τα δεξιά αναζητώντας το πρώτο στοιχείο με τιμή μεγαλύτερη ή ίση με την τιμή του pivot. Ύστερα, ο πίνακας σαρώνεται από τα δεξιά προς τα αριστερά αναζητώντας το πρώτο στοιχείο με τιμή μικρότερη ή ίση με την τιμή του pivot. Όταν εντοπισθούν δύο τέτοια στοιχεία, τότε αυτά ανταλλάσσονται, ώστε κατά το δυνατόν να τείνουν να πλησιάσουν προς την τελική τους θέση. Κατόπιν, συνεχίζουμε τις σαρώσεις προσπαθώντας να εντοπίσουμε άλλα παρόμοια ζεύγη και να τα ανταλλάξουμε. Κάποια στιγμή οι δύο δείκτες σάρωσης διασταυρώνονται. Τότε η σάρωση σταματά και ο pivot λαμβάνει την τελική του θέση εκτελώντας άλλη μία ανταλλαγή μεταξύ του pivot και του στοιχείου όπου σταμάτησε ο δείκτης της σάρωσης από δεξιά. Έτσι, η διαδικασία μπορεί να συνεχίσει στους δύο υποπίνακες κατά τα γνωστά. Το επόμενο σχήμα δείχνει τα βήματα του κώδικα μέχρι τον πρώτο διαμερισμό.

Τώρα ας προχωρήσουμε στην εύρεση της πολυπλοκότητας του αλγορίθμου. Κατ’αρχάς θα εξετάσουμε τη χειρότερη περίπτωση που είναι ευκολότερη, και στη συνέχεια την καλύτερη και τη μέση περιπτωση.

Πρόταση.
Η πολυπλοκότητα της γρήγορης ταξινόμησης είναι Θ($n^2$) στη χειρότερη περίπτωση.

Απόδειξη
Η περίπτωση αυτή συμβαίνει όταν σε πίνακα μεγέθους $n$, το επιλεγόμενο στοιχείο ως pivot είναι το μικρότερο ή το μεγαλύτερο, ώστε τα μεγέθη των δύο υποπινάκων που θα προκύψουν να είναι 0 και $n-1$ (αφού η μία θέση του συγκεκριμένου πίνακα θα καταληφθεί από τον ίδιο τον pivot). Έτσι, εύκολα προκύπτει η ακόλουθη αναδρομική εξίσωση:

Ο όρος $n$ του δεξιού σκέλους αντιστοιχεί στις συγκρίσεις που θα εκτελεσθούν κατά τη σάρωση του πίνακα (εντολές 4-5)¹¹Στην πραγματικότητα είναι δυνατό να εκτελεσθούν περισσότερες από $n$ συγκρίσεις, αλλά σε κάθε περίπτωση ο αριθμός των συγκρίσεων είναι μικρότερος από $2n$, γεγονός που δεν αλλάζει το τελικό συμπέρασμα.. Η ανωτέρω αναδρομική εξίσωση είναι εύκολη υπόθεση, καθώς διαδοχικά ισχύει:

Αθροίζοντας τα αριστερά και δεξιά σκέλη αυτών των εξισώσεων και θεωρώντας ότι $\mathrm{{\rm T}}(0)=\mathrm{{\rm T}}(1)=0$, προκύπτει ότι:

$\mathrm{\square }$

Πρόταση.
Η πολυπλοκότητα της γρήγορης ταξινόμησης είναι Θ($n\log n$) στην καλύτερη περίπτωση.

Απόδειξη
Για να αναλύσουμε την καλύτερη περίπτωση αρκεί να διαπιστώσουμε ότι αυτή συμβαίνει, όταν κάθε φορά ως pivot επιλέγεται ένα στοιχείο που λαμβάνοντας την τελική του θέση υποδιαιρεί τον πίνακα σε δύο υποπίνακες ίσου μεγέθους. Επομένως, ισχύει η αναδρομική εξίσωση:

με αρχικές συνθήκες $T(0)=T(1)=0$. Για την ευκολία της ανάλυσης υποθέτουμε ότι $n=2^k$, οπότε:

Η τελευταία αναδρομική εξίσωση είναι πλέον εύκολη υπόθεση, καθώς ισχύει διαδοχικά:

Αθροίζοντας τα αριστερά και δεξιά σκέλη αυτών των εξισώσεων προκύπτει ότι:

$\mathrm{\square }$

Πρόταση.
Η πολυπλοκότητα της γρήγορης ταξινόμησης είναι Θ($n\log n$) στη μέση περίπτωση.

Απόδειξη
Για να εξετάσουμε τη μέση περίπτωση θα υποθέσουμε ότι για $n$ στοιχεία, κάθε διάταξη των στοιχείων αυτών (όπου $n!$ είναι το πλήθος των διατάξεων) είναι ισοπίθανη. Επομένως, ο κάθε φορά επιλεγόμενος pivot τελικά επιλέγεται με τυχαίο τρόπο. Θα χειρισθούμε τη μέση περίπτωση με τη βοήθεια της επόμενης αναδρομικής εξίσωσης για $n\ge 2$:

με αρχικές συνθήκες $T(0)=T(1)=0$. Λόγω συμμετρίας και των αρχικών συνθηκών, η προηγούμενη αναδρομική εξίσωση μετασχηματίζεται σε:

Τώρα, τη σχέση αυτή πολλαπλασιάζουμε επί $n$ και προκύπτει:

Επίσης, στην ίδια σχέση αντικαθιστούμε το $n$ με $n-1$ και πολλαπλασιάζουμε με $n-1$, οπότε προκύπτει

Αφαιρώντας τα αντίστοιχα σκέλη των δύο τελευταίων εκφράσεων και εκτελώντας απλή άλγεβρα, προκύπτει:

Με διαδοχικές αντικαταστάσεις του $n$ με $n-1$ προκύπτει:

Αθροίζοντας αντίστοιχα τα αριστερά και τα δεξιά σκέλη και απλοποιώντας προκύπτει:

Επομένως, πρέπει να υπολογίσουμε το άθροισμα του δεξιού σκέλους:

Τελικώς, έχουμε:

$\mathrm{\square }$

Η γρήγορη ταξινόμηση δεν είναι επιτόπιος αλγόριθμος, δηλαδή δεν αρκείται στο χώρο του συγκεκριμένου πίνακα, αλλά χρειάζεται επιπλέον χώρο. Ο χώρος αυτός δεν φαίνεται καθαρά στον ανωτέρω κώδικα αλλά απαιτείται από το μεταγλωττιστή κατά την αναδρομή. Εύλογα προκύπτει η ερώτηση σχετικά με το μέγεθος αυτού του απαιτούμενου χώρου. Στη χειρότερη περίπτωση το μέγιστο βάθος της αναδρομής θα είναι $n-1$ κλήσεις, αριθμός υπερβολικός. Για το λόγο αυτό έχει σχεδιασθεί μία επαναληπτική εκδοχή της γρήγορης ταξινόμησης, δηλαδή μία εκδοχή που υλοποιεί την απαραίτητη στοίβα, όπου τοποθετούνται τα όρια του μικρότερου υποπίνακα, όπως φαίνεται στην επόμενη διαδικασία iterative_quicksort.

     procedure iterative_quicksort(left,right);
1.   repeat
2.      while (left<right) do
3.         i <-- left; j <-- r+1; pivot <-- A[left];
4.         repeat
5.            repeat i <-- i+1 until A[i]>=pivot;
6.            repeat j <-- j-1 until A[j]<=pivot;
7.            if i<j then swap(A[i],A[j]);
8.         until j<=i;
9.         swap(A[left],A[j]);
10.        if ((j-p)<(q-j)) then
11.           push(j+1); push(q); q <-- j-1
12.        else
13.           push(p); push(j-1); p <-- j+1
14.     if stack is empry then return
15.     pop(q); pop(p)
16.  until (false)

Πρόταση.
Η χωρική πολυπλοκότητα της γρήγορης ταξινόμησης είναι Θ($n\log n$) στη μέση περίπτωση.

Απόδειξη
Ο απαιτούμενος χώρος εκφράζεται από την αναδρομική εξίσωση:

Επομένως, υποθέτοντας ότι $n=2^k$, αρκεί να επιλύσουμε την εξίσωση:

$\mathrm{\square }$

Με τον όρο στατιστικά διάταξης (order statistics) εννοούμε την περίπτωση, όπου δεδομένου ενός πίνακα A με $n$ αταξινόμητα στοιχεία, πρέπει να αναζητήσουμε το μικρότερο, το μεγαλύτερο, το μεσαίο ή γενικά το $k$-οστό στοιχείο του πίνακα με βάση την τιμή του κλειδιού του. Παρά το γεγονός ότι το αντικείμενο είναι πρόβλημα αναζήτησης και όχι ταξινόμησης, θα το εξετάσουμε στο σημείο αυτό για λόγους που θα φανούν στη συνέχεια.

Ας αρχίσουμε από τα εύκολα, δηλαδή έστω ότι θέλουμε να βρούμε ταυτόχρονα το μικρότερο και το μεγαλύτερο στοιχείο ενός πίνακα. Η προφανής λύση είναι να εκτελέσουμε δύο σαρώσεις, μία σάρωση για την εύρεση του μικρότερου και στη συνέχεια μία σάρωση για την εύρεση του μεγαλύτερου. Είναι ευνόητο ότι η πολυπλοκότητα αυτής της πρώτης προσέγγισης είναι Θ($n$). Με τη διαδικασία που ακολουθεί προσπαθούμε με μία μόνο σάρωση να επιτύχουμε την ταυτόχρονη εύρεση των δύο στοιχείων που μας ενδιαφέρουν.

     procedure maxmin1
1.   max <-- A[1]; min <-- A[1];
2.   for i <-- 2 to n do
3.      if A[i]>max then max <-- A[i]
4.      if A[i]<min then min <-- A[i]
5.   return max, min

Η διαδικασία αυτή δεν παύει να είναι μία απλοϊκή προσέγγιση. Αν και γίνεται μία σάρωση του πίνακα, κάθε στοιχείο υποβάλλεται σε δύο συγκρίσεις, που όπως είπαμε είναι ένα σύνηθες βαρόμετρο. Η κατάσταση θα μπορούσε να βελτιωθεί, αν αντικαθιστούσαμε τις εντολές 3-4 με τις εντολές:

3.      if A[i]>max then max <-- A[i]
4.      else if A[i]<min then min <-- A[i]

Ωστόσο, και αυτή η εκδοχή μπορεί να αποδειχθεί ότι δεν βοηθά στη χειρότερη περίπτωση. Η επόμενη διαδικασία, που προσπαθεί να εκμεταλλευθεί την τεχνική του Διαίρει και Βασίλευε, υποθέτει ότι με τα ορίσματα i,j δίνουμε τα όρια του πίνακα και με τα ορίσματα fmax,fmin μας επιστρέφονται οι τιμές που μας ενδιαφέρουν. Επίσης, υποθέτουμε ότι η συνάρτηση max επιστρέφει το μέγιστο μεταξύ δύο στοιχείων, ενώ η συνάρτηση min επιστρέφει το ελάχιστο μεταξύ των δύο στοιχείων.

     procedure maxmin2(i,j,fmax,fmin)
1.   if i=j then
2.      max <-- A[i]; min <-- A[i];
3.   else if i=j-1 then
4.      if A[i]<A[j] then
5.         fmax <-- A[j]; fmin <-- A[i];
6.      else
7.         fmax <-- A[i]; fmin <-- A[j];
8.   else
9.      middle <-- (i+j)/2;
10.     maxmin2(i,mid,gmax,gmin);
11.     maxmin2(mid+1,j,hmax,hmin);
11.     fmax <-- max(gmax,hmax);
12.     fmin <-- min(gmin,hmin);

Έστω ότι το περιεχόμενο του πίνακα A είναι τα 9 στοιχεία 52, 12, 71, 56, 5, 10, 19, 90, 45. Στο επόμενο σχήμα απεικονίζεται ένα δένδρο με κόμβους που περιέχουν τα ορίσματα των κλήσεων. Διασχίζοντας το δένδρο με προτεραιότητα κατά βάθος (dfs) μπορούμε να αποτυπώσουμε την επακριβή σειρά των διαφόρων κλήσεων.

Πρόταση.
Η πολυπλοκότητα της maxmin2 είναι Θ($n$) στη χειρότερη περίπτωση.

Απόδειξη
Η πολυπλοκότητα της διαδικασίας αυτής μπορεί να ευρεθεί επιλύοντας την αναδρομική εξίσωση:

όπου οι σταθεροί όροι εκφράζουν το κόστος των συγκρίσεων στις εντολές 4 και 11-12. Θεωρώντας τη χειρότερη περίπτωση και ότι $n=2^k$ διαδοχικά έχουμε:

Επομένως, παρότι ο τελευταίος αλγόριθμος είναι βελτιωμένος δεν μπορεί να υπερβεί το όριο της γραμμικής πολυπλοκότητας Θ($n$). $\mathrm{\square }$  

Με τον όρο συγχώνευση (merging) εννοούμε την πράξη της δημιουργίας ενός νέου ταξινομημένου πίνακα που περιέχει όλα τα στοιχεία δύο (ή και περισσοτέρων) πινάκων, που είναι ήδη ταξινομημένοι. Η διαδικασία Merge που ακολουθεί υλοποιεί τη συγχώνευση δύο ταξινομημένων πινάκων A και B (με $n$ και $m$ ακεραίους αντίστοιχα) στον πίνακα C. Θεωρείται ότι οι δύο πίνακες έχουν και μία επιπλέον θέση που χρησιμεύει για την αποθήκευση ενός φρουρού (sentinel).

     procedure merge;
1.   i <-- 1; j <-- 1; A[n+1] <-- maxint; B[m+1] <-- maxint;
2.   for k <-- 1 to n+m do
3.      if A[i]<B[j] then
4.         C[k] <-- A[i]; i <-- i+1
5.      else
6.         C[k] <-- B[j]; j <-- j+1

Στην ουσία η συγχώνευση γίνεται με τη βοήθεια δύο δεικτών i και j που σαρώνουν τους δύο πίνακες και διαδοχικά συγκρίνουν στοιχεία από τους πίνακες A και B. Έτσι, κάθε φορά το μικρότερο στοιχείο μεταφέρεται στον πίνακα εξόδου C. Ο αναγνώστης μπορεί πολύ εύκολα να καταλάβει τη λειτουργία της διαδικασίας Merge και δεν χρειάζονται περισσότερες επεξηγήσεις. Από το βρόχο της εντολής 2, είναι προφανές ότι η πολυπλοκότητα της συγχώνευσης είναι Θ($n+m$), θεωρώντας φραγμένο από επάνω το κόστος της ερώτησης της εντολής 3-6.  

Στη φιλοσοφία της διαδικασίας αυτής βασίζεται μία σημαντικότατη μέθοδος ταξινόμησης, η ονομαζόμενη ταξινόμηση με ευθεία συγχώνευση (straight merge sort). Κατά καιρούς η μέθοδος αυτή έχει υλοποιηθεί με πλήθος τρόπων, όπως επαναληπτικά ή αναδρομικά, για λίστες ή πίνακες κοκ. Στη συνέχεια, ακολουθεί μία εκδοχή της για πίνακες, η οποία αποτελείται από δύο τμήματα: την αναδρομική merge_sort και τη merge. Στις εντολές 16-18 της merge_sort βρίσκεται το μεσαίο στοιχείο του πίνακα και εκτελούνται 2 κλήσεις στους δύο υποπίνακες που προκύπτουν. Από εδώ προκύπτει ότι η μέθοδος ανήκει στην οικογένεια των αλγορίθμων Διαίρει και Βασίλευε. Η διαδικασία merge που καλείται όταν προκύψουν στοιχειώδεις υπο-…-υπο-πίνακες αναλαμβάνει τις συγκρίσεις των στοιχείων και τα τακτοποιεί με τη βοήθεια ενός βοηθητικού πίνακα B.

     procedure merge(left,middle,right);
1.   first <-- left; second <-- middle+1; temp <-- left;
2.   while (first<=middle) and (second<=right) do
3.      if A[first]<=A[second] then
4.         B[temp] <-- A[first]; first <-- first+1;
5.      else
6.         B[temp] <-- A[second]; second <-- second+1;
7.      temp <-- temp+1
8.   if first<=middle then
9.      for k <-- first to middle do
10.        B[temp] <-- A[k]; temp <-- temp+1
11.  else
12.     for k <-- second to right do
13.        B[temp] <-- A[k]; temp <-- temp+1
14.  for k <-- left to right do A[k] <-- B[k]

     procedure merge_sort(left,right);
15.  if left<right then
16.     middle <-- (left+right) div 2;
17.     merge_sort(left,middle);
18.     merge_sort(middle+1,right);
19.     merge(left,middle,right)

Αν εφαρμόσουμε τις ανωτέρω διαδικασίες σε πίνακα με τα 9 γνωστά κλειδιά, τότε η mergesort θα κληθεί 17 φορές με τη σειρά που απεικονίζεται επάνω από κάθε κόμβο του επομένου σχήματος, ενώ μέσα σε κάθε κόμβο φαίνονται τα ορίσματα της αντίστοιχης κλήσης. Στο Σχήμα 8.7 φαίνονται 8 κλήσεις της merge, με την αντίστοιχη τάξη εκτός του κόμβου και τα ορίσματα εντός του κόμβου. Και στις δύο περιπτώσεις η διάσχιση του δένδρου ακολουθεί τη λογική της αναζήτησης με προτεραιότητα βάθους (dfs).

Πρόταση.
Η πολυπλοκότητα της merge_sort είναι Θ($n\log n$) στη χειρότερη περίπτωση.

Απόδειξη
Παρατηρώντας τη διαδικασία merge_sort εξάγουμε την επόμενη αναδρομική εξίσωση:

με αρχική συνθήκη $T(1)=1$, ενώ οι τρεις όροι του δεξιού σκέλους αντιστοιχούν στις εντολές 17-19. Συγκεκριμένα, το κόστος σε συγκρίσεις της εντολής 19 προκύπτει από όσα αναφέρθηκαν προηγουμένως για τη διαδικασία συγχώνευσης 2 πινάκων. Για την ευκολία της ανάλυσης υποθέτουμε ότι $n=2^k$, οπότε η ανωτέρω αναδρομική εξίσωση είναι πλέον εύκολη υπόθεση καθώς ισχύει διαδοχικά:

$\mathrm{\square }$

Η μέθοδος ταξινόμησης με ευθεία συγχώνευση αξίζει την προσοχή μας γιατί είναι πολύ ευσταθής (stable) μέθοδος, δηλαδή ανεξάρτητα από τη φύση των δεδομένων θα εκτελέσει τον ίδιο αριθμό συγκρίσεων στη μέση και τη χειρότερη περίπτωση. Το χαρακτηριστικό αυτό έρχεται σε αντίθεση με το μειονέκτημα της γρήγορης ταξινόμησης, που διακρίνεται από πολυπλοκότητα O($n^2$) για τη χειρότερη περίπτωση. Ωστόσο, το συμπέρασμα αυτό προκύπτει γιατί στην ανάλυση λάβαμε υπ’όψιν μας μόνο το πλήθος των εκτελούμενων συγκρίσεων. Σε μία πραγματική υλοποίηση, η χρήση του βοηθητικού πίνακα B και οι εκτελούμενες καταχωρήσεις είναι, επίσης, πράξεις μη αμελητέου χρονικού κόστους, οι οποίες επιβαρύνουν τη συνολική επίδοση. Τελικώς, αν και η ταξινόμηση με συγχώνευση δεν είναι ίσως η καλύτερη μέθοδος ταξινόμησης στην κύρια μνήμη, εν τούτοις αποτελεί τη βάση για μεθόδους εξωτερικής ταξινόμησης.

Η μέθοδος που προτάθηκε από τον Shell έχει βασικό χαρακτηριστικό ότι χρησιμοποιεί μία ακολουθία ακεραίων $h_1,h_2,\mathrm{\dots },h_k$, όπου ισχύει: $h_1>h_2>\mathrm{\dots }>h_{k-1}>h_k=1$ και γι’αυτό φέρει και την ονομασία ταξινόμηση με μειούμενες αυξήσεις (diminishing increment). Στην πράξη η μέθοδος λειτουργεί για οποιεσδήποτε τιμές της ακολουθίας $h_1,h_2,\mathrm{\dots },h_{k-1}$, αλλά θα πρέπει να ισχύει $h_k=1$.

Θα μπορούσε να υποστηριχθεί ότι η ταξινόμηση του Shell είναι μία παραλλαγή της ταξινόμησης με εισαγωγή. Ουσιαστικά, η μέθοδος αποτελείται από $k$ φάσεις, όπου στην $i$-οστή φάση (για $1\le i\le k$) θεωρείται το βήμα $h_i$, οπότε ακολουθώντας τη λογική της ταξινόμησης με εισαγωγή τίθενται σε σωστή διάταξη μεταξύ τους τα στοιχεία του πίνακα που απέχουν $h_i$ θέσεις. Προφανώς η $k$-οστή και τελευταία φάση είναι ένα κλασικό πέρασμα της ταξινόμησης με εισαγωγή που ολοκληρώνει τη διαδικασία. Πρέπει να τονισθεί ότι αποδεδειγμένα, αν ο πίνακας είναι ταξινομημένος με βάση κάποιο βήμα, τότε παραμένει ταξινομημένος με βάση το ίδιο βήμα ακόμη και αν εφαρμοσθούν ένα η περισσότερα επόμενα βήματα στη συνέχεια. Επίσης, καθώς η μέθοδος αυτή στηρίζεται στην ταξινόμηση με εισαγωγή, είναι και αυτή ευσταθής, δηλαδή δεν ανταλλάσσει αμοιβαία στοιχεία με ίσα κλειδιά.

Το παράδειγμα του Σχήματος 8.8 δείχνει το περιεχόμενο του πίνακα με τα γνωστά 9 κλειδιά και τον τρόπο ανταλλαγής τους, καθώς ο πίνακας ταξινομείται σταδιακά με 3 βήματα μεγέθους 4, 2 και 1. Μεταξύ των γραμμών που δείχνουν το πέρας κάθε φάσης, παρουσιάζονται οι εκτελούμενες ανταλλαγές στοιχείων του πίνακα. Στο παράδειγμα αυτό, επίσης, παρατηρούμε χαρακτηριστικά πως ο πίνακας παραμένει ταξινομημένος με βήμα 4 ακόμη και μετά το πέρας της φάσης με βήμα 2.

Ο ψευδοκώδικας που ακολουθεί παρουσιάζει αλγοριθμικά το προηγούμενο σκεπτικό. Ο ψευδοκώδικας δεν είναι αρκετά γενικός, καθώς θεωρεί μία απλή ακολουθία με 3 βήματα μεγέθους 4, 2 και 1, ώστε να συμφωνεί με το παράδειγμα. Η δεύτερη παρατήρηση είναι ότι για επιπλέον λόγους ευκολίας θεωρεί ότι στα αριστερά του πίνακα υπάρχουν τρεις επιπλέον θέσεις, όπου τοποθετούνται κόμβοι φρουροί με τιμές ίσες προς τα βήματα, αντίστοιχα.

     procedure shellsort;
1.   h[1] <-- 4; h[2] <-- 2; h[3] <-- 1;
2.   for m <--  1 to 3 do
3.      k <-- h[m]; s <-- -k
4.      for i <-- k+1 to n do
5.         x <-- A[i]; j <-- i-k;
6.         if s=0 then s <-- -k;
7.         s <-- s+1; A[s] <-- x;
8.         while x<Α[j] do
9.            A[j+k] <-- A[j]; j <-- j-k
10.        A[j+k] <-- x

Η απλή αυτή λογική της μεθόδου του Shell πάσχει κατά το ότι η ακολουθία των ακεραίων παραμένει μία παράμετρος προς βελτιστοποίηση. Δηλαδή, έχουν προταθεί και έχουν αναλυθεί με περισσότερη ή λιγότερη δυσκολία αρκετές ακολουθίες, αλλά θα μπορούσε να προταθεί μία νέα ακολουθία και να αποδειχθεί ότι αυτή είναι καλύτερη από κάθε προηγούμενη και πιθανώς η βέλτιστη. Στη συνέχεια, θα παρουσιάσουμε την ανάλυση της χειρότερης περίπτωσης για την ακολουθία που προτάθηκε από τον ίδιο τον Shell και δίνεται από τις σχέσεις: $h_1=\lfloor n/2\rfloor$ και $h_{i+1}=\lfloor h_i/2\rfloor$.

Πρόταση.
Η πολυπλοκότητα της shellsort είναι Θ($n^2$) στη χειρότερη περίπτωση για την ακολουθία του Shell, όπου $h_1=\lfloor n/2\rfloor$ και $h_{i+1}=\lfloor h_i/2\rfloor$.

Απόδειξη
Για να αποδείξουμε ότι η πολυπλοκότητα της χειρότερης περίπτωσης για την ακολουθία του Shell είναι Θ($n^2$), πρώτα θα αποδείξουμε ότι ισχύει το Ω($n^2$) και μετά το Ο($n^2$). Έστω ότι $n=2^k$, οπότε κάθε βήμα είναι άρτιος αριθμός εκτός από το τελευταίο βήμα που ισούται με τη μονάδα. Έστω, επίσης, ότι αρχικά τα $n/2$ μεγαλύτερα στοιχεία τοποθετούνται στις άρτιες θέσεις, ενώ τα $n/2$ μικρότερα στοιχεία τοποθετούνται στις περιττές θέσεις. Μέχρι να φθάσουμε στο τελευταίο βήμα, όλα τα $n/2$ μεγαλύτερα στοιχεία είναι ακόμη στις άρτιες θέσεις και όλα τα $n/2$ στοιχεία είναι στις μικρότερες θέσεις. Επομένως, το $i$-οστό μικρότερο στοιχείο (για $i\le n/2$) βρίσκεται στην $(2i-1)$-οστή θέση πριν αρχίσει το τελικό πέρασμα και πρέπει να εκτελεσθούν $i-1$ ανταλλαγές μέχρι να φθάσει στην τελική του θέση. Άρα, για όλα τα $n/2$ μικρότερα στοιχεία θα απαιτηθούν ${\sum }_{i=1}^{n/2}(i-1)=\frac{n^2-n}{8}=\mathrm{\Omega }(n^2)$ ανταλλαγές. Το Σχήμα 8.9 απεικονίζει το παράδειγμα που περιγράφηκε πριν.

Για να αποδείξουμε το δεύτερο σκέλος, αρκεί να θεωρήσουμε ότι κατά το πέρασμα με βήμα $h_k$, ουσιαστικά εκτελείται μία ταξινόμηση με εισαγωγή (τετραγωνικής πολυπλοκότητας) για ένα σύνολο $n/h_k$ στοιχείων. Επομένως, για το σύνολο των περασμάτων με αυτό το βήμα η πολυπλοκότητα είναι Ο$(h_k{(n/h_k)}^2)$ = O$(n^2/h_k)$. Επομένως για το σύνολο των βημάτων προκύπτει η πολυπλοκότητα $O({\sum }_{i+1}^t{n}^2/h_t)=O(n^2{\sum }_{i+1}^{t}1/h_t)$. Καθώς η ακολουθία των βημάτων είναι γεωμετρική, έπεται ότι . Έτσι προκύπτει το ζητούμενο, δηλαδή ότι η πολυπλοκότητα της ταξινόμησης του Shell για τη δεδομένη ακολουθία είναι Ο($n^2$). $\mathrm{\square }$  

Στη βιβλιογραφία έχουν παρουσιασθεί πολλές εναλλακτικές προτάσεις για την ακολουθία των βημάτων και έχουν αναλυθεί. Για παράδειγμα, για την ακολουθία $1,3,7,\mathrm{\dots },2^k-1$ του Hibbard, αν και εικάζεται από πειραματικά αποτελέσματα ότι η πολυπλοκότητα είναι Ο($n^{5/4}$), το όριο που έχει αποδειχθεί είναι Θ($n^{3/2}$).

Μέχρι στιγμής εξετάσθηκαν μέθοδοι ταξινόμησης με πολυπλοκότητα της τάξης O($n^2$) ή Ο($n\log n$). Τι εκφράζει η κάθε μία από αυτές τις τάξεις πολυπλοκότητας; Ο μέθοδος της ταξινόμησης με εισαγωγή, της ταξινόμησης με επιλογή και της ταξινόμησης με ανταλλαγή (bubblesort) είναι οι λεγόμενες ευθείες (straight) μέθοδοι που είναι απλές στην κατανόηση, την κωδικοποίηση και την ανάλυση, αλλά αποτελούν μία οικογένεια αργών αλγορίθμων ταξινόμησης. Για τις μεθόδους αυτές ισχύει η επόμενη θεώρηση.  

Δοθέντος ενός πίνακα Α με $n$ διακριτά στοιχεία λέγεται ότι υπάρχει μία αντιστροφή (inversion), αν ισχύει $A[i]>A[j]$ για κάποια . Με απλά λόγια, στην ακολουθία $S=3,14,1,5,9$ οι αντιστροφές είναι (3,1), (14,1), (14,5) και(14,9).  

Πρόταση.
Κάθε αλγόριθμος που σε κάθε βήμα απομακρύνει το πολύ μία αντιστροφή απαιτεί $n(n-1)/2$ βήματα στη χειρότερη περίπτωση και $n(n-1)/4$ βήματα στη μέση περίπτωση.  

Απόδειξη.
Αν υποθέσουμε ότι ο πίνακας Α περιέχει μία τυχαία διάταξη των τιμών $1,2,\mathrm{\dots },n$ από το σύνολο των $n!$ διατάξεων. Ορίζουμε ως ανεστραμμένο (reverse) του πίνακα Α, τον πίνακα ${\mathrm{A}}^R=(\mathrm{A}[n],\mathrm{A}[n-1],\mathrm{\dots },\mathrm{A}[1])$. Σημειώνεται ότι ${({\mathrm{A}}^R)}^R=\mathrm{A}$, ενώ για $n>1$ δεν υπάρχει περίπτωση κάποιος πίνακας να αποτελεί αντίστροφο του εαυτού του. Έτσι οι $n!$ διατάξεις μπορούν να χωρισθούν σε $n!/2$ ζεύγη, όπου κάθε ζεύγος αποτελείται από μία διάταξη και την αντεστραμμένη της. Υπάρχουν $n(n-1)/2$ ζεύγη τιμών $i,j$, όπου . Για κάθε τέτοιο ζεύγος τιμών ($i,j$) και για κάθε ζεύγος διάταξης και της αντεστραμμένης της ($\mathrm{A},{\mathrm{A}}^R$), θα υπάρχει μόνο μία αντιστροφή στη μία διάταξη από τις δύο του κάθε ζεύγους. Επομένως ο συνολικός αριθμός αντιστροφών σε όλες τις διατάξεις είναι $n(n-1)/2$, ενώ η μέση τιμή των αντιστροφών είναι $n(n-1)/4$. $\mathrm{\square }$  

Πρόταση.
Δεδομένου ενός πίνακα που περιέχει μία τυχαία διάταξη με $n$ στοιχεία, το άθροισμα των αποστάσεων που διανύονται από τα στοιχεία κατά την ταξινόμησή τους είναι $(n^2-1)/3$.  

Απόδειξη.
Ας υποθέσουμε ότι ο πίνακας Α περιέχει μία τυχαία διάταξη των τιμών $1,2,\mathrm{\dots },n$. Δοθέντος ενός τυχαίου στοιχείου Α[$j$], η απόσταση που θα διανύσει είναι $\mathrm{A}[j]-j$. Επομένως θεωρώντας το σύνολο των στοιχείων ισχύει ότι η μέση τιμή της απόστασης ισούται με:

Συνεπώς, η μέση διανυόμενη απόσταση είναι:

Οι όροι εντός του αθροίσματος είναι ίδιοι για συμπληρωματικές τιμές του $j$ και επομένως ισχύει:

Συνεπώς, ένας αλγόριθμος ταξινόμησης που μετακινεί τα στοιχεία κατά ένα σταθερό αριθμό θέσεων σε κάθε βήμα απαιτεί Ο($n^2$) βήματα. $\mathrm{\square }$  

Τελικά τίθεται το ερώτημα «Πόσο γρήγορα μπορεί μία μέθοδος να ταξινομήσει έναν πίνακα;». Θα αποδειχθεί ότι, όταν μία μέθοδος ταξινόμησης στηρίζεται μόνο σε συγκρίσεις και ανταλλαγές κλειδιών, τότε στη χειρότερη περίπτωση δεν μπορεί να ταξινομήσει σε χρόνο κατώτερο του Ο($n\log n$).

Πριν την απόδειξη της σχετική πρότασης είναι αναγκαίο να περιγραφεί η διαδικασία ταξινόμησης με ένα δένδρο αποφάσεων (decision tree). Ένα μονοπάτι του δένδρου δείχνει μία πιθανή διαδοχή από υπολογισμούς που ο αλγόριθμος πιθανώς να ακολουθήσει. Για παράδειγμα, ας υποτεθεί ότι πρέπει να ταξινομηθούν τρία κλειδιά: τα $k_1,k_2$ και $k_3$ αντίστοιχα. Η σειρά εισόδου των κλειδιών είναι $k_1,k_2$ και $k_3$ που φαίνεται στο δένδρο αποφάσεων ως (1,2,3). Αρχικά, συγκρίνονται τα κλειδιά $k_1$ και $k_2$. Αν , τότε η σειρά (1,2,3) δεν αλλάζει, αλλιώς γίνεται (2,1,3).

Στο επόμενο σχήμα φαίνονται όλα τα πιθανά ενδεχόμενα που μπορούν να συμβούν σε έναν αλγόριθμο ταξινόμησης ανάλογα με τη σειρά σύγκρισης των κλειδιών στο δένδρο. Από το σχήμα αυτό φαίνεται ότι το δένδρο αποφάσεων είναι ένα δυαδικό δένδρο. Τα φύλλα του δένδρου είναι αριθμημένα από Ι ως VI και αποτελούν τα μοναδικά σημεία τερματισμού κάθε αλγορίθμου ταξινόμησης. Το δένδρο αυτό έχει 3!=6 φύλλα που εξασφαλίζει ότι ο αλγόριθμος βρίσκει πάντοτε τη διάταξη εκείνη που αντιστοιχεί στην ταξινομημένη σειρά.  

Πρόταση.
Κάθε δένδρο αποφάσεων που ταξινομεί $n$ διακεκριμένα κλειδιά έχει ύψος τουλάχιστον $\log n!$.  

Απόδειξη.
Ένα δένδρο αποφάσεων έχει $n!$ φύλλα που αντιστοιχούν σε κάθε μία από τις $n!$ διατάξεις των $n$ κλειδιών. Ας υποτεθεί ότι το δένδρο είναι πλήρες και ότι το ύψος του είναι $h$. Τότε ο αριθμός των φύλλων είναι $2^{h-1}$, οπότε συνεπάγεται ότι $n!=2^{h-1}$. Λογαριθμώντας και τα δύο μέλη της σχέσης προκύπτει:

Το δένδρο δεν είναι πλήρες και, άρα, η πρόταση ισχύει. $\mathrm{\square }$  

Πρόταση.
Κάθε αλγόριθμος που ταξινομεί κάνοντας μόνο συγκρίσεις και ανταλλαγές κλειδιών έχει στη χειρότερη περίπτωση χρόνο τάξης Ο($n\log n$).  

Απόδειξη.
Πρέπει να αποδειχθεί ότι σε κάθε δένδρο αποφάσεων με $n$! φύλλα υπάρχει ένα μονοπάτι μήκους $c\cdot n\log n$, όπου $c$ είναι μία σταθερά. Από την προηγούμενη πρόταση προκύπτει ότι κάθε μονοπάτι είναι μήκους $\log n!$. Αντικαθιστώντας με βάση τον τύπο του Stirling προκύπτει:

$\mathrm{\square }$

Ας υποθέσουμε ότι δίνεται ένας πίνακας Α με $n$ στοιχεία, που λαμβάνουν τιμές από 1 μέχρι $k$, όπου . Θα εκτελέσουμε μία ταξινόμηση με τη βοήθεια ενός βοηθητικού πίνακα C μεγέθους $k$, ενώ το αποτέλεσμα θα αποθηκευθεί στον πίνακα B. Με απλά λόγια, η ταξινόμηση αυτή δεν είναι επιτόπια. Δίνεται ο επόμενος ψευδοκώδικας και θα σχολιασθεί στη συνέχεια με τη βοήθεια ενός παραδείγματος.

     procedure countsort
1.   for i <-- 1 to k do C[i] <-- 0;
2.   for i <-- 1 to n do C[A[i]] <-- C[A[i]]+1;
3.   for i <-- 2 to k do C[i] <-- C[i]+C[i-1]
4.   for i <-- n downto 1 do
5.      B[C[A[i]]] <-- A[i]; C[A[i]] <-- C[A[i]]-1

Έστω $n=8,k=7$ και ο πίνακας Α με το περιεχόμενο του Πίνακα 8.1. Με την εντολή 2 καταμετρώνται οι εμφανίσεις της κάθε τιμής (από τις $k$) και τοποθετούνται σε αντίστοιχες θέσεις του πίνακα C. Με την εντολή 3 σαρώνεται ο πίνακας C και προκύπτει η νέα μορφή του C, όπου κάθε θέση προκύπτει ως το άθροισμα των τιμών των δύο προηγούμενων θέσεων. Το περιεχόμενο του πίνακα C μετά το πέρας των εντολών 2-3 δίνονται στoν Πίνακα 8.2. Με το βρόχο της εντολής 4, στον πίνακα Β τοποθετείται η ζητούμενη ταξινομημένη ακολουθία και τερματίζει ο αλγόριθμος.

Παρατηρούμε ότι ο ψευδοκώδικας αποτελείται από τέσσερις διαδοχικούς βρόχους. Εξ αυτών οι δύο εκτελούν $n$ επαναλήψεις, ενώ άλλοι δύο εκτελούν $k$ επαναλήψεις. Ευνόητο είναι ότι η πολυπλοκότητα του αλγορίθμου είναι Θ($n+k$). Με την παραδοχή ότι , έπεται ότι η πολυπλοκότητα είναι Θ($n$). Επιτύχαμε δηλαδή ένα γραμμικό αλγόριθμο ταξινόμησης σε αντίθεση με τα προηγούμενα; Η ερώτηση είναι παγίδα γιατί στην παρούσα περίπτωση (α) ο αλγόριθμος δεν στηρίζεται στις συγκρίσεις και (β) αν $k\gg n$, τότε προφανώς δεν ισχύει το τελικό συμπέρασμα.  

Τώρα ας προσέξουμε τον επόμενο κώδικα. Οι πρώτες δύο εντολές είναι πανομοιότυπες με τις πρώτες δύο εντολές της διαδικασίας countsort, αλλά στη συνέχεια υπάρχει διαφορά. Πιο συγκεκριμένα, δεν υπάρχει ο βοηθητικός πίνακας Β και, επίσης παρατηρούμε ένα διπλό βρόχο στις εντολές 4-6. Αν εκτελέσουμε τον αλγόριθμο, έστω και με χαρτί και μολύβι, θα διαπιστώσουμε ότι ουσιαστικά εκτελεί την ίδια λειτουργία με την προηγούμενη διαδικασία.

     procedure countsort2
1.   for i <-- 1 to k do C[i] <-- 0;
2.   for i <-- 1 to n do C[A[i]] <-- C[A[i]]+1;
3.   i <-- 0;
4.   for j <-- 1 to k do
5.      for m <-- C[j] down to 1 do
6.         i <-- i+1; A[i] <-- j

Πρόταση.
Η πολυπλοκότητα της countsort2 είναι Θ($n+k$) στη χειρότερη περίπτωση.

Απόδειξη.
Η περίπτωση θυμίζει το παράδειγμα που είχαμε επιλύσει στο Κεφάλαιο 1.5 (όπου το άνω όριο του βρόχου δεν ήταν ένας κλασικός δείκτης αλλά το περιεχόμενο μίας θέσης του πίνακα). Σύμφωνα, λοιπόν, με μία πρώτη προσέγγιση, με βάση τα όρια των βρόχων for μπορούμε να φθάσουμε στο συμπέρασμα ότι η πολυπλοκότητα είναι Ο($kn$), επειδή $n$ είναι η τιμή του C[i] στην εντολή 5 στη χειρότερη περίπτωση. Ωστόσο, η ανάλυση αυτή δεν είναι σφικτή.

Ο εξωτερικός βρόχος for της εντολής 4 είναι συγκεκριμένος, δηλαδή έχουμε $k$ επαναλήψεις. Η εντολή 6 θα εκτελεσθεί ακριβώς $n$ φορές και όχι $kn$. Αυτό προκύπτει με βάση την εξής παρατήρηση: Ας θεωρήσουμε την $j$-οστή επανάληψη του εξωτερικού βρόχου. Ο έλεγχος του εσωτερικού βρόχου for θα εκτελεσθεί C[j]+1 φορές. Επομένως, ο συνολικός αριθμός ελέγχων στο σημείο αυτό είναι:

Συνεπώς και πάλι καταλήγουμε στο ίδιο συμπέρασμα ως προς την πολυπλοκότητα της διαδικασίας. $\mathrm{\square }$

Η ταξινόμηση με βάση τη ρίζα (radix sort) είναι μία γενίκευση της ταξινόμησης με μέτρημα. Με απλά λόγια, έστω ότι δίνεται προς ταξινόμηση ένας πίνακας με $n$ ακεραίους μέγεθους $d$ ψηφίων. Εκτελούμε μία ταξινόμηση με μέτρημα ως προς το τελευταίο, δηλαδή το λιγότερο σημαντικό ψηφίο (least significant digit). Έτσι, προκύπτει μία νέα μορφή του πίνακα, που και πάλι ταξινομούμε με μέτρημα αλλά αυτή τη φορά ως προς το δεύτερο ψηφίο από το τέλος. Η διαδικασία αυτή συνεχίζεται και τελειώνει, όταν ο προκύπτων πίνακας ταξινομείται ως προς το πρώτο, δηλαδή το περισσότερο σημαντικό ψηφίο (most significant digit).

Σημειώνεται ότι στην ταξινόμηση με βάση τη ρίζα δεν υπάρχει περιορισμός ως προς το εύρος τιμών των κλειδιών, όπως υπάρχει στην ταξινόμηση με μέτρημα (η γνωστή παράμετρος $k$). Όμως, όταν λαμβάνεται σε κάθε κλήση το αντίστοιχο ψηφίο, τότε εκεί προφανώς τα ψηφία λαμβάνουν τιμές εντός του διαστήματος 1-9, και έτσι συνιστάται η χρήση της ταξινόμησης με μέτρημα. Η μέθοδος θα μπορούσε να εφαρμοσθεί και σε συμβολοσειρές, όπου κάθε χαρακτήρας θα λάμβανε τιμές στο διάστημα a-z ή α-ω (δηλαδή, 26 ή 24 διαφορετικές τιμές αντίστοιχα). Από το χρησιμοποιούμενο, λοιπόν, αριθμητικό σύστημα (δηλαδή το δεκαδικό, δυαδικό κλπ. σε περίπτωση αριθμών ή το διάστημα 1-24/26 σε περίπτωση χαρακτήρων) προκύπτει η ονομασία της μεθόδου (radix). Η επόμενη συνοπτικότατη διαδικασία καταγράφει αυτήν την περιγραφή.

   procedure radixsort
1. for i <-- 1 to d do
2.    countsort(d)

Έστω ότι δίνονται προς ταξινόμηση ο πίνακας A με τα γνωστά 9 κλειδιά 52, 12, 71, 56, 5, 10, 19, 90 και 45, όπως φαίνεται στοn Πίνακα 8.3. Αν καλέσουμε την countsort της εντολής 2 με όρισμα d=1 (θεωρούμε ότι η αρίθμηση των ψηφίων αρχίζει από το λιγότερο σημαντικό), τότε θα προκύπτει η δεύτερη μορφή του πίνακα, ενώ με τη δεύτερη κλήση της countsort και όρισμα d=2 θα προκύψει η τελική μορφή του πίνακα.

Η ανάλυση της πολυπλοκότητας της ταξινόμησης με βάση της ρίζα είναι εύκολη υπόθεση. Εφόσον η ταξινόμηση με μέτρημα έχει γραμμική πολυπλοκότητα Θ($n+k$), έπεται ότι η πολυπλοκότητα της ταξινόμησης με βάση τη ρίζα είναι Θ($dn+dk$). Θεωρώντας το $d$ σταθερά, προκύπτει και πάλι γραμμική πολυπλοκότητα.

Η ταξινόμηση με κάδους (bucket sort) στηρίζεται στην υπόθεση ότι δίνονται προς ταξινόμηση $n$ αριθμοί που ανήκουν στο διάστημα [0,1). Το διάστημα αυτό υποδιαιρείται σε $n$ ίσα υποδιαστήματα (τους λεγόμενους κάδους), όπου κατανέμονται τα ισάριθμα στοιχεία προς ταξινόμηση. Επειδή, θεωρούμε ότι τα στοιχεία υπακούουν σε μία ομοιόμορφη κατανομή, δεν αναμένουμε να ανήκουν πάρα πολλά στοιχεία σε ένα συγκεκριμένο υποδιάστημα. Η τελική ταξινομημένη ακολουθία προκύπτει ταξινομώντας τα στοιχεία του κάθε κάδου και κατόπιν λαμβάνοντας τους κάδους στη σειρά. Η επόμενη διαδικασία περιγράφει όσα αναφέραμε. Εκτός του πίνακα Α με τα $n$ στοιχεία, χρησιμοποιείται και ένας βοηθητικός πίνακας Β με επίσης $n$ θέσεις για τη δημιουργία συνδεδεμένων λιστών.

     procedure bucketsort
1.   for i <-- 1 to n do insert(A[i],B[floor(n*A[i])])
2.   for i <-- 1 to n do insertsort(B[i])
3.   return (B[1], B[2], ..., B[n])

Για παράδειγμα, έστω ότι δίνεται ο πίνακας Α με τα γνωστά $n=9$ στοιχεία από τα προηγούμενα παραδείγματα, διαιρεμένα δια 100. Θεωρούμε έναν πίνακα Β με 9 θέσεις, όποτε τα υποδιαστήματα που αντιστοιχούν στις θέσεις του πίνακα Β είναι [0-0,11), [0,11-0,22), [0,22-0,33), …, [0,88-1). Το Σχήμα 8.11 απεικονίζει την κατάσταση μετά το πέρας της εντολής 1, οπότε έχουν εισαχθεί όλα τα στοιχεία στις αντίστοιχες συνδεδεμένες λίστες. Εννοείται ότι στη συνέχεια τα στοιχεία κάθε λίστας πρέπει να ταξινομηθούν, ώστε να δοθούν στην έξοδο.

Πρόταση.
Η πολυπλοκότητα της bucketsort είναι γραμμική στη μέση περίπτωση.

Απόδειξη.
Προκειμένου να βρούμε την πολυπλοκότητα της μεθόδου πρέπει να εστιάσουμε στην εντολή 2, γιατί προφανώς η εντολή 1 έχει γραμμικό κόστος. Στην εντολή 2 ουσιαστικά εκτελούμε $n$ ανεξάρτητες ταξινομήσεις με εισαγωγή με $n_i$ στοιχεία η κάθε μία, όπου το $n_i$ είναι μία τυχαία μεταβλητή. Επομένως, το συνολικό κόστος των εντολών 1-2 είναι:

Ορίζουμε μία τυχαία μεταβλητή $X_{ij}$ που ισούται με 1, αν το στοιχείο $A[j]$ κατανέμεται στον $i$-οστό κάδο, ενώ αλλιώς ισούται με 0 (όπου $1\le i,j\le n$). Άρα ισχύει $n_i={\sum }_{j=1}^n{X}_{ij}$ και συνεπώς:

Θα επιλύσουμε τα δύο αθροίσματα ξεχωριστά. Η τυχαία μεταβλητή $X_{ij}$ ισούται με 1 με πιθανότητα $1/n$. Επομένως:

Σε σχέση με το δεύτερο άθροισμα ισχύει ότι $k\ne j$ και επομένως οι δύο τυχαίες μεταβλητές είναι ανεξάρτητες. Από το Κεφάλαιο 2.1 γνωρίζουμε ότι: $\mathrm{E}[XY]=\mathrm{E}[X]\times \mathrm{E}[Y]$. Συνεπώς:

Άρα, αντικαθιστώντας προκύπτει:

Επιστρέφοντας στην αρχική σχέση έχουμε:

$\mathrm{\square }$

Στη συνέχεια, ακολουθεί μία κομψότερη απόδειξη του προηγούμενου αποτελέσματος.

Πρόταση.
Η πολυπλοκότητα της bucketsort είναι γραμμική στη μέση περίπτωση.

Απόδειξη.
Η πιθανότητα ένα συγκεκριμένο στοιχείο να κατανεμηθεί στον $i$-οστό κάδο είναι $p=1/n$. Η πιθανότητα υπακούει μία δυωνυμική κατανομή με προσδοκητή τιμή $\mathrm{E}[n_i]=np=1$ και απόκλιση $\mathrm{Var}[{\mathrm{n}}_{\mathrm{i}}]=np(1-p)=1-1/n$. Από το Κεφάλαιο 2.1 γνωρίζουμε ότι για οποιαδήποτε τυχαία μεταβλητή ισχύει:

Συνεπώς, ισχύει: