Σε αυτό το σεμινάριο, θα μάθετε πώς λειτουργεί η καταμέτρηση ταξινόμησης. Επίσης, θα βρείτε λειτουργικά παραδείγματα καταμέτρησης ταξινόμησης σε C, C ++, Java και Python.
Η καταμέτρηση ταξινόμησης είναι ένας αλγόριθμος ταξινόμησης που ταξινομεί τα στοιχεία ενός πίνακα μετρώντας τον αριθμό των εμφανίσεων κάθε μοναδικού στοιχείου στον πίνακα. Η μέτρηση αποθηκεύεται σε μια βοηθητική συστοιχία και η ταξινόμηση γίνεται με χαρτογράφηση της καταμέτρησης ως ευρετήριο του βοηθητικού πίνακα.
Πώς λειτουργεί το Counting Sort;
- Μάθετε το μέγιστο στοιχείο (αφήστε το
max) από τη δεδομένη συστοιχία.
Δεδομένος πίνακας - Αρχικοποιήστε έναν πίνακα μήκους
max+1με όλα τα στοιχεία 0. Αυτός ο πίνακας χρησιμοποιείται για την αποθήκευση του αριθμού των στοιχείων στον πίνακα.
Πίνακας μέτρησης - Αποθηκεύστε την καταμέτρηση κάθε στοιχείου στον αντίστοιχο ευρετήριό τους σε
countπίνακα.
Για παράδειγμα: εάν η μέτρηση του στοιχείου 3 είναι 2 τότε, το 2 αποθηκεύεται στην 3η θέση του πίνακα μέτρησης. Εάν το στοιχείο "5" δεν υπάρχει στον πίνακα, τότε το 0 αποθηκεύεται στην 5η θέση.
Πλήθος κάθε αποθηκευμένου στοιχείου - Αποθηκεύστε το αθροιστικό άθροισμα των στοιχείων του πίνακα μετρήσεων. Βοηθά στην τοποθέτηση των στοιχείων στο σωστό ευρετήριο του ταξινομημένου πίνακα.
Αθροιστικός αριθμός - Βρείτε το ευρετήριο κάθε στοιχείου του αρχικού πίνακα στον πίνακα μετρήσεων. Αυτό δίνει τον αθροιστικό αριθμό. Τοποθετήστε το στοιχείο στο ευρετήριο που υπολογίζεται όπως φαίνεται στο παρακάτω σχήμα.
Μετρώντας είδος - Αφού τοποθετήσετε κάθε στοιχείο στη σωστή του θέση, μειώστε τον αριθμό του κατά ένα.
Αλγόριθμος μέτρησης ταξινόμησης
countSort (array, size) max <- εύρεση μεγαλύτερου στοιχείου σε array αρχικοποίηση πίνακα μετρήσεων με όλα τα μηδενικά για j <- 0 στο μέγεθος βρείτε το συνολικό πλήθος κάθε μοναδικού στοιχείου και αποθηκεύστε την καταμέτρηση στο jth index σε array array για i <- 1 για να βρείτε το αθροιστικό άθροισμα και να το αποθηκεύσετε στον ίδιο πίνακα μετρήσεων για το j <- μέγεθος έως 1 επαναφέρετε τα στοιχεία στη συστοιχία μείωσης του αριθμού κάθε στοιχείου που αποκαθίσταται κατά 1
Παραδείγματα Python, Java και C / C ++
Python Java C C ++ # Counting sort in Python programming def countingSort(array): size = len(array) output = (0) * size # Initialize count array count = (0) * 10 # Store the count of each elements in count array for i in range(0, size): count(array(i)) += 1 # Store the cummulative count for i in range(1, 10): count(i) += count(i - 1) # Find the index of each element of the original array in count array # place the elements in output array i = size - 1 while i>= 0: output(count(array(i)) - 1) = array(i) count(array(i)) -= 1 i -= 1 # Copy the sorted elements into original array for i in range(0, size): array(i) = output(i) data = (4, 2, 2, 8, 3, 3, 1) countingSort(data) print("Sorted Array in Ascending Order: ") print(data)
// Counting sort in Java programming import java.util.Arrays; class CountingSort ( void countSort(int array(), int size) ( int() output = new int(size + 1); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); // Initialize count array with all zeros. for (int i = 0; i < max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Driver code public static void main(String args()) ( int() data = ( 4, 2, 2, 8, 3, 3, 1 ); int size = data.length; CountingSort cs = new CountingSort(); cs.countSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
// Counting sort in C programming #include void countingSort(int array(), int size) ( int output(10); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) // The size of count must be at least (max+1) but // we cannot declare it as int count(max+1) in C as // it does not support dynamic memory allocation. // So, its size is provided statically. int count(10); // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countingSort(array, n); printArray(array, n); )
// Counting sort in C++ programming #include using namespace std; void countSort(int array(), int size) ( // The size of count must be at least the (max+1) but // we cannot assign declare it as int count(max+1) in C++ as // it does not support dynamic memory allocation. // So, its size is provided statically. int output(10); int count(10); int max = array(0); // Find the largest element of the array for (int i = 1; i max) max = array(i); ) // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countSort(array, n); printArray(array, n); )
Περίπλοκο
Χρόνος πολυπλοκότητας:
Υπάρχουν κυρίως τέσσερις κύριοι βρόχοι. (Η εύρεση της μεγαλύτερης τιμής μπορεί να γίνει εκτός της συνάρτησης.)
| για βρόχο | ώρα καταμέτρησης |
|---|---|
| 1ος | O (μέγ.) |
| 2ος | O (μέγεθος) |
| 3ος | O (μέγ.) |
| 4ος | O (μέγεθος) |
Συνολική πολυπλοκότητα = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Χειρότερη περίπλοκη περίπτωση:
O(n+k) - Καλύτερη πολυπλοκότητα περιπτώσεων:
O(n+k) - Μέση πολυπλοκότητα περιπτώσεων:
O(n+k)
Σε όλες τις παραπάνω περιπτώσεις, η πολυπλοκότητα είναι η ίδια γιατί ανεξάρτητα από το πώς τοποθετούνται τα στοιχεία στη συστοιχία, ο αλγόριθμος περνά τους n+kχρόνους.
Δεν υπάρχει σύγκριση μεταξύ οποιουδήποτε στοιχείου, επομένως είναι καλύτερο από τις τεχνικές ταξινόμησης με βάση τη σύγκριση. Όμως, είναι κακό εάν οι ακέραιοι αριθμοί είναι πολύ μεγάλοι επειδή πρέπει να δημιουργηθεί ο πίνακας αυτού του μεγέθους.
Διαστημική πολυπλοκότητα:
Η διαστημική πολυπλοκότητα του Counting Sort είναι O(max). Όσο μεγαλύτερη είναι η γκάμα των στοιχείων, τόσο μεγαλύτερη είναι η πολυπλοκότητα του χώρου.
Καταμέτρηση εφαρμογών ταξινόμησης
Το είδος καταμέτρησης χρησιμοποιείται όταν:
- υπάρχουν μικρότεροι ακέραιοι αριθμοί με πολλαπλούς αριθμούς.
- η γραμμική πολυπλοκότητα είναι η ανάγκη.
