Η μέτρηση Ταξινόμηση είναι ένας αποτελεσματικός αλγόριθμος ταξινόμησης που χρησιμοποιείται για τη διαλογή ακέραιων δεδομένων σε ένα συγκεκριμένο εύρος. Λειτουργεί μετρώντας τον αριθμό των εμφανίσεων κάθε τιμής και στη συνέχεια υπολογίζοντας τις θέσεις κάθε στοιχείου στη ταξινομημένη διάταξη. Αυτή η μέθοδος είναι ιδιαίτερα χρήσιμη όταν το εύρος των δεδομένων εισόδου δεν είναι σημαντικά μεγαλύτερο από τον αριθμό των στοιχείων που ταξινομούνται.

Πώς λειτουργεί η Μέτρηση

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

Παράδειγμα υπολογισμού

Υποθέστε ότι έχουμε τη σειρά: [4, 2, 8, 3, 3, 1]. Το εύρος των τιμών είναι από 1 έως 8. Η διαδικασία καταμέτρησης οδηγεί σε μια σειρά καταμέτρησης:

[0, 1, 2, 2, 1, 0, 0, 0, 1, 1]

Αυτό δείχνει τη συχνότητα κάθε αριθμού. Ο αλγόριθμος υπολογίζει στη συνέχεια τις αθροιστικές μετρήσεις για τον προσδιορισμό των θέσεων:

[0, 1, 3, 5, 6, 6, 6, 6, 7]

Χρησιμοποιώντας αυτά, η ταξινομημένη σειρά γίνεται: [1, 2, 3, 3, 4, 8].

Σενάρια εφαρμογής

Το είδος μέτρησης είναι κατάλληλο για σενάρια όπου τα δεδομένα εισόδου αποτελούνται από ακέραιους εντός ενός γνωστού, περιορισμένου εύρους. Χρησιμοποιείται συχνά σε:

  • Ταξινόμηση των βαθμών των μαθητών (π.χ., 0-100)
  • Οργάνωση δεδομένων σε ανάλυση συχνότητας
  • Ταξινόμηση μικρών ακέραιων σε ενσωματωμένα συστήματα
  • Είδος εφαρμογής του ⁇ διξ ως υπορουτίνα

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