Ebben az oktatóanyagban megtudhatja, hogyan működik a rendezés számlálása. Ezenkívül talál működő példákat a rendezés számlálására C, C ++, Java és Python nyelven.
A számláló rendezés olyan rendezési algoritmus, amely a tömb elemeit úgy rendezi, hogy megszámolja a tömbben található egyes egyedi elemek előfordulásainak számát. A számlálást egy kiegészítő tömbben tárolják, és a rendezés a számlálás feltérképezésével történik a segéd tömb indexeként.
Hogyan működik a rendezés számlálása?
- Tudja meg a maximális elemet (legyen az
max) az adott tömbből.
Adott tömb - Inicializáljon egy hosszúságú tömböt
max+1minden elemmel. Ezt a tömböt a tömbben található elemek számának tárolására használják.
Count tömb - Tárolja az egyes elemek számát a megfelelő indexben a
counttömbben
. Például: ha a 3. elem száma 2, akkor a 2 a számlálótömb 3. pozíciójában tárolódik. Ha az "5" elem nincs a tömbben, akkor a 0 az 5. pozícióban lesz tárolva.
Az egyes tárolt elemek száma - Tárolja a számláló tömb elemeinek összesített összegét. Segít abban, hogy az elemeket a rendezett tömb helyes indexébe helyezzük.
Halmozott szám - Keresse meg az eredeti tömb egyes elemeinek indexét a számláló tömbben. Ez megadja a kumulatív számot. Helyezze az elemet az alábbi ábra szerint kiszámított indexhez.
Számolási rendezés - Miután minden elemet a megfelelő helyzetbe helyezett, csökkentse eggyel a számát.
Számlálás rendezési algoritmus
countingSort (tömb, méret) max <- keresse meg a tömb legnagyobb elemét inicializálja a számláló tömböt az összes nullával a j <- 0 méretre, keresse meg az egyes egyedi elemek összes számát, és tárolja a számot a j-dik indexben a szám tömbben i <- 1 max megtalálni a kumulatív összeget és tárolni magában a count tömbben j <- méretig 1-ig visszaállítani az elemeket, hogy az egyes elemekkel visszaállított tömbcsökkenések száma 1
Példák Python, Java és 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); )
Bonyolultság
Időkomplexumok:
Főleg négy fő hurok van. (A legnagyobb érték megtalálása a függvényen kívül is elvégezhető.)
| for-loop | a számlálás ideje |
|---|---|
| 1 | O (max) |
| 2. | O (méret) |
| 3 | O (max) |
| 4 | O (méret) |
Összetettség = O(max)+O(size)+O(max)+O(size)=O(max+size)
- Legrosszabb eset komplexitás:
O(n+k) - Legjobb eset komplexitás:
O(n+k) - Átlagos esetösszetétel:
O(n+k)
A fenti esetek mindegyikében a bonyolultság ugyanaz, mert függetlenül attól, hogy az elemek hogyan helyezkednek el a tömbben, az algoritmus n+kidőkön megy keresztül .
Nincs összehasonlítás egyetlen elem között sem, ezért jobb, mint az összehasonlításon alapuló rendezési technikák. De rossz, ha az egész számok nagyon nagyok, mert akkora tömböt kell készíteni.
Tér összetettsége:
A Counting Sort térbeli összetettsége O(max). Nagyobb elemtartomány, nagyobb a tér bonyolultsága.
Az alkalmazások rendezése
A számlálási rendezést akkor alkalmazzák, ha:
- vannak kisebb, többszörös számok.
- a lineáris komplexitás az igény.
