Šajā rakstā mēs apspriedīsim skaitīšanas kārtošanas algoritmu. Skaitīšanas kārtošana ir šķirošanas paņēmiens, kura pamatā ir atslēgas starp konkrētiem diapazoniem. Programmatūras inženieru kodēšanas vai tehniskajās intervijās plaši tiek uzdoti šķirošanas algoritmi. Tāpēc ir svarīgi apspriest tēmu.
Šis šķirošanas paņēmiens neveic šķirošanu, salīdzinot elementus. Tas veic kārtošanu, saskaitot objektus, kuriem ir atšķirīgas galvenās vērtības, piemēram, jaukšana. Pēc tam tas veic dažas aritmētiskas darbības, lai aprēķinātu katra objekta indeksa pozīciju izvades secībā. Skaitīšanas kārtošana netiek izmantota kā vispārējas nozīmes kārtošanas algoritms.
Skaitīšanas kārtošana ir efektīva, ja diapazons nav lielāks par kārtojamo objektu skaitu. To var izmantot, lai kārtotu negatīvās ievades vērtības.
Tagad apskatīsim skaitīšanas kārtošanas algoritmu.
Algoritms
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
Skaitīšanas kārtošanas algoritma darbība
Tagad apskatīsim skaitīšanas kārtošanas algoritma darbību.
Lai saprastu skaitīšanas kārtošanas algoritma darbību, ņemsim nešķirotu masīvu. Izmantojot piemēru, būs vieglāk saprast skaitīšanas kārtošanu.
Lai masīva elementi ir -
1. Atrodiet maksimālo elementu no dotā masīva. Ļaujiet maks būt maksimālajam elementam.
2. Tagad inicializējiet garuma masīvu maks + 1 kurā ir visi 0 elementi. Šis masīvs tiks izmantots, lai saglabātu elementu skaitu dotajā masīvā.
java un šūpoles
3. Tagad mums ir jāsaglabā katra masīva elementa skaits atbilstošā indeksā skaitīšanas masīvā.
Elementa skaits tiks saglabāts kā - Pieņemsim, ka masīva elements '4' parādās divas reizes, tātad elementa 4 skaits ir 2. Tādējādi 2 tiek saglabāts pie 4.thskaitīšanas masīva pozīcija. Ja masīvā nav neviena elementa, novietojiet 0, t.i., pieņemsim, ka elementa '3' masīvā nav, tāpēc 0 tiks saglabāts 3.rdpozīciju.
Tagad saglabājiet kumulatīvo summu skaitīt masīva elementi. Tas palīdzēs novietot elementus pareizajā sakārtotā masīva rādītājā.
Tāpat skaitīšanas masīva kumulatīvais skaits ir -
4. Tagad atrodiet katra sākotnējā masīva elementa indeksu
Pēc elementa novietošanas savā vietā samaziniet tā skaitu par vienu. Pirms 2. elementa ievietošanas tā skaits bija 2, bet pēc novietošanas pareizajā vietā 2. elementa jaunais skaits ir 1.
Tāpat pēc šķirošanas masīva elementi ir -
Tagad masīvs ir pilnībā sakārtots.
Skaitīšanas kārtošanas sarežģītība
Tagad apskatīsim skaitīšanas laika sarežģītību labākajā, vidējā un sliktākajā gadījumā. Mēs redzēsim arī skaitīšanas kārtošanas telpas sarežģītību.
1. Laika sarežģītība
| Lieta | Laiks | Sarežģītība |
|---|---|---|
| Labākais gadījums | O(n+k) | |
| Vidējais gadījums | O(n+k) | |
| Sliktākajā gadījumā | O(n+k) |
Visos iepriekš minētajos gadījumos skaitīšanas kārtošanas laika sarežģītība ir vienāda. Tas ir tāpēc, ka algoritms iet cauri n+k reizes neatkarīgi no tā, kā elementi ir izvietoti masīvā.
Skaitīšanas kārtošana ir labāka nekā uz salīdzināšanu balstītās šķirošanas metodes, jo skaitīšanas kārtošanā elementi nav salīdzināmi. Bet, ja veseli skaitļi ir ļoti lieli, skaitīšanas kārtošana ir slikta, jo ir jāizveido šāda izmēra masīvi.
2. Telpas sarežģītība
| Kosmosa sarežģītība | O (maks.) |
| Stabils | JĀ |
- Skaitīšanas kārtošanas telpas sarežģītība ir O(max). Jo lielāks elementu klāsts, jo lielāka ir telpas sarežģītība.
Skaitīšanas šķirošanas ieviešana
Tagad apskatīsim skaitīšanas programmu šķirošanu dažādās programmēšanas valodās.
Programma: Uzrakstiet programmu skaitīšanas kārtošanai C valodā.
#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;></=> Izvade
rakhi sawant
Tātad, tas viss par rakstu. Cerams, ka raksts jums būs noderīgs un informatīvs.
Šis raksts neaprobežojās tikai ar algoritmu. Mēs arī apspriedām kārtošanas sarežģītības skaitīšanu, darbību un ieviešanu dažādās programmēšanas valodās.