Ebben a cikkben a számlálási rendezési algoritmust tárgyaljuk. A számláló rendezés egy olyan rendezési technika, amely meghatározott tartományok közötti kulcsokon alapul. A szoftvermérnökök számára készített kódolási vagy technikai interjúk során széles körben felteszik a kérdést a rendezési algoritmusoknak. Ezért fontos a téma megvitatása.
Ez a rendezési technika nem végez elemek összehasonlításával történő rendezést. A rendezést úgy hajtja végre, hogy megszámolja a különböző kulcsértékekkel rendelkező objektumokat, mint például a hash. Ezt követően végrehajt néhány aritmetikai műveletet, hogy kiszámítsa az egyes objektumok indexpozícióját a kimeneti sorozatban. A számláló rendezést nem használják általános célú rendezési algoritmusként.
A számláló rendezés akkor hatásos, ha a tartomány nem nagyobb, mint a rendezendő objektumok száma. Használható a negatív bemeneti értékek rendezésére.
Most pedig lássuk a számolási rendezés algoritmusát.
Algoritmus
countingSort(array, n) // 'n' is the size of array max = find maximum element in the given array create count array with size maximum + 1 Initialize count array with all 0's for i = 0 to n find the count of every unique element and store that count at ith position in the count array for j = 1 to max Now, find the cumulative sum and store it in count array for i = n to 1 Restore the array elements Decrease the count of every restored element by 1 end countingSort
Számláló rendezési algoritmus működése
Most pedig lássuk a számláló rendezési algoritmus működését.
ha különben bash
A számláló rendezési algoritmus működésének megértéséhez vegyünk egy rendezetlen tömböt. Egy példán keresztül könnyebb lesz megérteni a számlálási rendezést.
Legyen a tömb elemei -
1. Keresse meg az adott tömbből a maximális elemet! Hadd max legyen a maximális elem.
java kivételkezelés
2. Most inicializálja a hosszúságú tömböt max + 1 amelynek mind a 0 eleme van. Ez a tömb az adott tömb elemeinek számának tárolására szolgál.
3. Most el kell tárolnunk az egyes tömbelemek számát a megfelelő indexen a count tömbben.
Egy elem száma a következőképpen kerül tárolásra: - Tegyük fel, hogy a '4' tömbelem kétszer jelenik meg, tehát a 4-es elem száma 2. Így a 2 a 4-ben van tárolva.tha számlálótömb pozíciója. Ha bármely elem nem szerepel a tömbben, tegye a 0-t, azaz tegyük fel, hogy a '3' elem nincs a tömbben, így a 0 a 3-ban lesz tárolvardpozíció.
hogyan lehet zenét letölteni
Most tárolja a kumulatív összegét számol tömbelemek. Segít az elemeket a rendezett tömb megfelelő indexére helyezni.
Hasonlóképpen, a count tömb összesített száma -
4. Most keresse meg az eredeti tömb minden elemének indexét
Miután az elemet a helyére helyezte, csökkentse a számát eggyel. A 2. elem elhelyezése előtt a száma 2 volt, de a megfelelő pozícióba helyezés után a 2. elem új száma 1.
Hasonlóképpen a rendezés után a tömb elemei:
Most a tömb teljesen rendezve van.
multiplexer
A rendezés bonyolultságának számolása
Most lássuk a számlálási rendezés időbeli összetettségét legjobb, átlagos és legrosszabb esetben. Látni fogjuk a számolási rendezés térbeli összetettségét is.
1. Időbonyolultság
| Ügy | Idő | Bonyolultság |
|---|---|---|
| Legjobb eset | O(n + k) | |
| Átlagos eset | O(n + k) | |
| Legrosszabb esetben | O(n + k) |
A számlálási rendezés időbeli összetettsége minden fenti esetben azonos. Ez azért van, mert az algoritmus átmegy n+k alkalommal, függetlenül attól, hogy az elemek hogyan helyezkednek el a tömbben.
A számlálási rendezés jobb, mint az összehasonlításon alapuló rendezési technikák, mivel a számlálási rendezésben nincs összehasonlítás az elemek között. De ha az egész számok nagyon nagyok, a számlálási rendezés rossz, mert ekkora tömböket kell létrehozni.
2. A tér összetettsége
| A tér összetettsége | O(max.) |
| Stabil | IGEN |
- A számolási rendezés térkomplexitása O(max). Minél nagyobb az elemek köre, annál nagyobb a tér összetettsége.
Számláló rendezés megvalósítása
Most lássuk a számláló programok rendezését különböző programozási nyelveken.
Program: Írjon programot a számlálási rendezés megvalósítására C nyelven!
#include int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 16 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; printf('%d ', a[i]); main() a[]="{" 11, 30, 24, 7, 31, }; n="sizeof(a)/sizeof(a[0]);" printf('before sorting are -
'); printarr(a, n); countsort(a, printf('
after return 0; pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-12.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 11 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; cout< <a[i]<<' '; main() a[]="{" 31, 11, 42, 7, 30, }; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting are -
'; printarr(a, n); countsort(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-13.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C#.</p> <pre> using System; class CountingSort { static int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } static void countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 3 i++) { a[i]="output[i];" store the sorted elements into main array } static void printarr(int[] a, int n) * function to print i; for (i="0;" i < n; console.write(a[i] + ' '); main() int[] a="{" 43, 31, 2, 7, 10, 1, 5, 6, }; n="a.Length;" console.write('before sorting are -
'); printarr(a,n); countsort(a,n); console.write('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-14.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in Java.</p> <pre> class CountingSort { int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); //int max = 42; int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 41 i++) { a[i]="output[i];" store the sorted elements into main array } * function to print void printarray(int a[], int n) i; for (i="0;" i < n; system.out.print(a[i] + ' '); public static main(string args[]) a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="a.length;" countingsort c1="new" countingsort(); system.out.println('
before sorting are - c1.printarray(a, n); c1.countsort(a,n); system.out.println('
after system.out.println(); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-15.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in PHP.</p> <pre> <?php function getMax($a, $n) { $max = $a[0]; for($i = 1; $i $max) $max = $a[$i]; } return $max; //maximum element from the array } function countSort(&$a, $n) // function to perform counting sort { $LeftArray = array($n + 1); $max = getMax($a, $n); $count = array($max + 1); //create count array with size [max+1] for ($i = 0; $i <= $max; ++$i) { $count[$i] = 0; // Initialize count array with all zeros } for ($i = 0; $i < $n; $i++) // Store the count of each element { $count[$a[$i]]++; } for($i = 1; $i= 0; $i--) { $output[$count[$a[$i]] - 1] = $a[$i]; $count[$a[$i]]--; // decrease count for same numbers } for($i = 0; $i<$n; $i++) { $a[$i] = $output[$i]; //store the sorted elements into main array } } /* Function to print the array elements */ function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 9, 28, 22, 5, 29, 14, 37, 28, 9 ); $n = count($a); echo 'Before sorting array elements are - <br>'; printArray($a, $n); countSort($a,$n); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-16.webp" alt="Counting Sort"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed counting sort complexity, working, and implementation in different programming languages.</p> <hr></n;></=></pre></n;></=></pre></n;></=></pre></n;></=> Kimenet
Szóval ennyi a cikkről. Reméljük, hogy a cikk hasznos és informatív lesz az Ön számára.
városok Ausztráliában
Ez a cikk nem csak az algoritmusra korlátozódott. Megbeszéltük a rendezés bonyolultságának számlálását, a működést és a különböző programozási nyelveken történő megvalósítást is.