În acest tutorial, veți afla cum funcționează numărarea sortării. De asemenea, veți găsi exemple de lucru de numărare sortare în C, C ++, Java și Python.
Numărarea sortării este un algoritm de sortare care sortează elementele unui tablou prin numărarea numărului de apariții ale fiecărui element unic din tablou. Numărul este stocat într-o matrice auxiliară și sortarea se face prin maparea numărării ca un index al matricei auxiliare.
Cum funcționează numărarea sortării?
- Aflați elementul maxim (lăsați-l să fie
max) din matricea dată.
Matrice date - Inițializați o matrice de lungime
max+1cu toate elementele 0. Această matrice este utilizată pentru stocarea numărului de elemente din matrice.
Numără matrice - Stocați numărul fiecărui element la indexul respectiv în
countmatrice
De exemplu: dacă numărul elementului 3 este 2, atunci 2 este stocat în poziția a 3-a matricei de numărare. Dacă elementul "5" nu este prezent în matrice, atunci 0 este stocat în poziția a 5-a.
Numărul fiecărui element stocat - Stocați suma cumulativă a elementelor matricei de numărare. Ajută la plasarea elementelor în indexul corect al matricei sortate.
Numărul cumulativ - Găsiți indexul fiecărui element al matricei originale din matricea de numărare. Acest lucru oferă numărul cumulativ. Plasați elementul la indexul calculat așa cum se arată în figura de mai jos.
Sortare numărare - După plasarea fiecărui element în poziția corectă, micșorați numărul acestuia cu unul.
Algoritmul de sortare de numărare
countingSort (matrice, dimensiune) max <- găsiți cel mai mare element din matrice inițializați matrice de numărare cu toate zerourile pentru j <- 0 până la dimensiune găsiți numărul total al fiecărui element unic și stocați numărul la indexul j în matrice de numărare pentru i <- 1 pentru a găsi maxim suma cumulativă și a o stoca în matrice de numărare în sine pentru j <- dimensiunea până la 1 restabiliți elementele pentru a matricea numărul de scădere al fiecărui element restaurat cu 1
Exemple Python, Java și 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); )
Complexitate
Complexități de timp:
Există în principal patru bucle principale. (Găsirea celei mai mari valori se poate face în afara funcției.)
| pentru buclă | timpul numărării |
|---|---|
| Primul | O (max) |
| Al 2-lea | O (dimensiune) |
| A treia | O (max) |
| Al 4-lea | O (dimensiune) |
Complexitate generală = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Cel mai prost caz de complexitate:
O(n+k) - Complexitatea celui mai bun caz:
O(n+k) - Complexitatea medie a cazurilor:
O(n+k)
În toate cazurile de mai sus, complexitatea este aceeași, deoarece indiferent de modul în care elementele sunt plasate în matrice, algoritmul trece de-a lungul n+ktimpului.
Nu există comparație între elemente, deci este mai bine decât tehnici de sortare bazate pe comparație. Dar, este rău dacă numerele întregi sunt foarte mari, deoarece ar trebui făcută matricea de acea dimensiune.
Complexitatea spațială:
Complexitatea spațială a numărării sortării este O(max). Cu cât este mai mare gama de elemente, cu atât este mai mare complexitatea spațiului.
Numărarea aplicațiilor de sortare
Sortarea numărării este utilizată atunci când:
- există numere întregi mai mici cu mai multe numere.
- complexitatea liniară este necesitatea.
