Sorting Algorithms


Radix Sort

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

Οι περισσότεροι ψηφιακοί υπολογιστές εσωτερικά αντιπροσωπεύουν όλα τους τα δεδομένα ως ηλεκτρονικές αναπαραστάσεις δυαδικών αριθμών, έτσι η επεξεργασία των ψηφίων των ακεραίων αναπαραστάσεων από ομάδες δυαδικών αναπαραστάσεων είναι πιο βολική. Δύο κατηγορίες της ταξινόμησης βάσης είναι η ταξινόμηση βάσης από το λιγότερο σημαντικό ψηφίο (LSD) και από το περισσότερο σημαντικό ψηφίο (MSD). Η πρώτη επεξεργάζεται τις αναπαραστάσεις ακεραίων αρχίζοντας από το λιγότερο σημαντικό ψηφίο και μετακινείται προς το περισσότερο σημαντικό ψηφίο. Η ταξινόμηση βάσης MSD εργάζεται με τον αντίθετο τρόπο.

Ο αλγόριθμος LSD τυπικά χρησιμοποιεί την ακόλουθη σειρά ταξινόμησης, μικρότερα κλειδιά τοποθετούνται πριν από τα μεγαλύτερα και κλειδιά ίδιου μήκους ταξινομούνται λεξικογραφικά. Αυτό έχει ως αποτέλεσμα τη συνηθισμένη σειρά αναπαράστασης ακεραίων όπως η ακολουθία 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

Ο αλγόριθμος MSD χρησιμοποιεί λεξικογραφική ταξινόμηση, η οποία είναι κατάλληλη για ταξινόμηση συμβολοσειρών, όπως λέξεις ή αναπαραστάσεις ακεραίων με προκαθορισμένο μήκος. Μία ακολουθία όπως η {b, c, d, e, f, g, h, i, j, ba} θα ταξινομηθεί λεξικογραφικά ως {b, ba, c, d, e, f, g, h, i, j}. Αν χρησιμοποιηθεί η παραπάνω τεχνική για ταξινόμηση ακεραίων, τότε οι αναπαραστάσεις ακεραίων από 1 μέχρι 10 θα δώσουν το αποτέλεσμα 1, 10, 2, 3, 4, 5, 6, 7, 8, 9, διότι τα μικρότερα κλειδιά στοιχίζονται αριστερά και συμπληρώνονται με κενούς χαρακτήρες στα δεξιά ώστε να φτάσουν το μήκος των μεγαλύτερων κλειδιών.

Pseudocode

 1.RadixSort(A[0..N-1],maxDigitSymbols)
 2.
mod ← 10

 3.
dev ← 1

 4.
for i=0:maxDigitSymbols

 5.
for j=0:N-1

 6.
bucket ←

 7.
counter[bucket].add(A[j])

 8.
j ← j + 1

 9.
end for

10.
pos ← 0

11.
for j=0:N-1

12.
value ← null

13.
while (value = counter[j].poll() ≠ null)

14.
A[pos] ← value

15.
pos ← pos + 1

16.
end while

17.
j ← j + 1

18.
end for

19.
dev ← dev * 10

20.
mod ← mod * 10

21.
i ← i + 1

22.
end for

23.
return A

24.end

Applet

Java applet that demonstrates radix sort algorithm.

Example

Έστω ο πίνακας A=[9 179 139 38 10 5 36] με μέγιστο αριθμό ψηφίων maxDigitSymbols=3. Οι μεταβλητές mod και dev παίρνουν τις τιμές 10 και 1 αντίστοιχα.

Επανάληψη 1 κατά i

Το i αντιστοιχεί στο πλήθος των ψηφίων και ξεκινάει από την τιμή 0 για τις μονάδες

Επανάληψη κατά j

Ο δείκτης j σαρώνει τον πίνακα Α και υπολογίζει το υπόλοιπο της διαίρεσης κάθε στοιχείου του Α με το mod, το αποτέλεσμα διαιρείται με το dev και κρατάμε το ακέραιο μέρος το οποίο ανατίθεται στη μεταβλητή bucket. Στη συνέχεια το στοιχείο του Α προστίθεται στη λίστα counter[bucket].

j=0, bucket=(A[0]%10)/1=9%10=9, counter[9]={9}
j=1, bucket=(A[1]%10)/1=179%10=9, counter[9]={9, 179}
…
j=6, bucket=(A[6]%10)/1=36%10=6, counter[6]={36}

Η λίστα counter αποτελείται από 10 λίστες και είναι η ακόλουθη.

counter={ {10}, {}, {}, {}, {}, {5}, {36}, {}, {38}, {9,179,139} }

Το pos=0 και ξεκινάει η επανάληψη για j=0.

Επανάληψη κατά j

Το value αρχικά γίνεται null και στη συνέχεια λαμβάνει την τιμή του στοιχείου που βρίσκεται στην κεφαλή της λίστας counter[j]. Όσο το value είναι διάφορο του null η τιμή του value ανατίθεται στο Α[pos] και το pos αυξάνεται κατά 1.

value=counter[0].poll()=10≠null A[0]=10
value=null
j=1, value=counter[1].poll()=null
…
j=9, value=counter[9].poll()=9≠null A[4]=9
value=counter[9].poll()=179≠null A[5]=179
value=counter[9].poll()=139≠null A[6]=139
value=null

Μετά το πέρας της επανάληψης κατά j ο πίνακας Α έχει ταξινομηθεί με βάση τις μονάδες.

A=[10 5 36 38 9 179 139]
Επανάληψη 2 κατά i

Το i γίνεται 1 το οποίο αντιστοιχεί στις δεκάδες, το mod=100 και dev=10.

Επανάληψη κατά j
j=0, bucket=(A[0]%100)/10=(10%100)/10=10/10=1, counter[1]={10}
j=1, bucket=(A[1]%100)/10=(5%100)/10=5/10=0, counter[0]={5}
…
j=6, bucket=(A[6]%100)/10=(139%100)/10=39/10=3, counter[3]={36,38,139}
counter={ {5,9}, {10}, {}, {36,38,139}, {}, {}, {}, {179}, {}, {}}
pos=0,
j=0, value=counter[0].poll()=5≠null A[0]=5
value=counter[0].poll()=9≠null A[1]=9
value=null
…
j=9, value=counter[9].poll()=null

Ο πίνακας Α έχει ταξινομηθεί αλλά ο αλγόριθμος θα συνεχίσει. Αυτό συμβαίνει στο συγκεκριμένο παράδειγμα και όχι πάντα.

A=[5 9 10 36 38 139 179]
Επανάληψη 3 κατά i

Το i τέλος γίνεται 2 το οποίο αντιστοιχεί στις εκατοντάδες, το mod=1000 και dev=100.

…

Ο πίνακας Α στο τέλος της 3ης επανάληψης δεν αλλάζει.

A=[5 9 10 36 38 139 179]