aaaa

a

Υβριδική μέθοδος ταξινόμησης

 

English

Μελέτη του συγκριτικού συγχωνευτικού αλγόριθμου Merge Sort και του μη συγκριτικού καταμετριτικού αλγόριθμου Counting Sort με σκοπό τον συνδυασμό τους σε έναν ενιαίο αλγόριθμο βέλτιστης απόδοσης.

Θεωρητικό μοντέλο, πρακτική εφαρμογή  στην κβάντιση χρώματος με τον αλγόριθμο Color Quantization και πειραματικά δεδομένα.

του Άγγελου Σπάρταλη
Μηχανολόγου Μηχανικού Ε.Μ.Π.
angelosspartalis@yahoo.gr

ΔΕΚΕΜΒΡΙΟΣ 2015

Ο αλγόριθμος Merge sort (παχιά γκρίζα καμπύλη) και ο αλγόριθμος Counting sort (λεπτές καμπύλες χρωματισμένες ανάλογα με το εύρος των αριθμών που ταξινομούνται) όπως αποδίδουν στην ταξινόμηση φυσικών αριθμών τυχαίας κατανομής. Κάντε κλικ στην εικόνα του διαγράμματος για να μεγαλώσει. Δείτε επίσης το διάγραμμα κατανάλωσης μνήμης εδώ και τα αναλυτικά δεδομένα εδώ.

Η υβριδικής μεθόδος συνδυάζει τους αλγόριθμους Merge sort και Counting sort στην ταξινόμηση φυσικών αριθμών τυχαίας κατανομής αποδίδοντας βέλτιστα. Κάντε κλικ στην εικόνα του διαγράμματος για να μεγαλώσει.Δείτε επίσης το διάγραμμα κατανάλωσης μνήμης εδώ και τα αναλυτικά δεδομένα εδώ.

κατεβάστε το άρθρο
από το  www.academia.ecu  ή από  εδώ

κατεβάστε το αρχείο SPARTA_sort.zip

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

διάγραμμα 6

Κατά την κβάντιση χρώματος εικόνων ανάλυσης 4K, από τα 24 bit στα 8 bit, o Merge sort ταξινομεί εντός της κόκκινης περιοχής, ο Counting sort εντός της κίτρινης περιοχής και η Υβριδική μέθοδος εντός του μπλέ περιγράμματος, αποδίδοντας 161% ταχύτερα από τον Merge sort και 15% ταχύτερα από τον Counting sort. Και οι τρεις αλγόριθμοι καταναλώνουν την ίδια ποσότητα προσωρινής μνήμης (64 MB). Δείτε επίσης τα αναλυτικά δεδομένα εδώ.