logo

Razvrščanje s štetjem – Vadnice za podatkovne strukture in algoritme

Kaj je razvrščanje s štetjem?

Štetje Razvrsti je ki ne temelji na primerjanju algoritem za razvrščanje, ki dobro deluje, ko je obseg vhodnih vrednosti omejen. Še posebej je učinkovito, če je obseg vhodnih vrednosti majhen v primerjavi s številom elementov, ki jih je treba razvrstiti. Osnovna ideja v ozadju Štetje Razvrsti je prešteti pogostost vsakega ločenega elementa v vhodni matriki in uporabite te informacije za postavitev elementov na njihove pravilno razvrščene položaje.

Kako deluje algoritem razvrščanja s štetjem?

Korak 1 :



  • Ugotovite, maksimum element iz podane matrike.

Iskanje največjega elementa v inputArray[]

2. korak:

  • Inicializiraj a countArray[] dolžine največ+1 z vsemi elementi kot 0 . Ta matrika bo uporabljena za shranjevanje pojavitev elementov vhodne matrike.

Inicializiraj countArray[]



3. korak:

  • V countArray[] , shranijo število vsakega edinstvenega elementa vhodne matrike pri njihovih ustreznih indeksih.
  • Na primer: Število elementov 2 v vhodnem polju je 2. Torej, trgovina 2 pri indeksu 2 v countArray[] . Podobno število elementov 5 v vhodnem polju je 1 , torej trgovina 1 pri indeksu 5 v countArray[] .

Ohranite število vsakega elementa v countArray[]

4. korak:



  • Shranite kumulativna vsota oz predpona vsota elementov countArray[] z početjem countArray[i] = countArray[i – 1] + countArray[i]. To bo pomagalo pri postavljanju elementov vhodne matrike na pravi indeks v izhodni matriki.

Shranite kumulativno vsoto v countArray[]

5. korak:

  • Ponavljaj od konca vhodne matrike in ker prečkanje vhodne matrike od konca ohranja vrstni red enakih elementov, zaradi česar na koncu ta algoritem razvrščanja stabilno .
  • Nadgradnja izhodnaMatrika[ ŠteviloMatrika[ vhodnaMatrika[i] ] – 1] = vhodnaMatrika[i] .
  • Prav tako posodobite countArray[ inputArray[i] ] = countArray[ inputArray[i] ] – -.

5

6. korak: Za i = 6 ,

linux ukaz za zip

Nadgradnja izhodnaMatrika[ ŠteviloMatrika[ vhodnaMatrika[6] ] – 1] = vhodnaMatrika[6]
Prav tako posodobite countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

Postavitev inputArray[6] na pravilen položaj v outputArray[]

7. korak: Za i = 5 ,

Nadgradnja izhodnaMatrika[ ŠteviloMatrika[ vhodnaMatrika[5] ] – 1] = vhodnaMatrika[5]
Prav tako posodobite countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

Postavitev inputArray[5] na pravilen položaj v outputArray[]

8. korak: Za i = 4 ,

Nadgradnja izhodnaMatrika[ ŠteviloMatrika[ vhodnaMatrika[4] ] – 1] = vhodnaMatrika[4]
Prav tako posodobite countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

Postavitev inputArray[4] na pravilen položaj v outputArray[]

9. korak: Za i = 3 ,

Nadgradnja izhodnaMatrika[ ŠteviloMatrika[ vhodnaMatrika[3] ] – 1] = vhodnaMatrika[3]
Prav tako posodobite countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

Postavitev inputArray[3] na pravilen položaj v outputArray[]

10. korak: Za i = 2 ,

Nadgradnja izhodnaMatrika[ ŠteviloMatrika[ vhodnaMatrika[2] ] – 1] = vhodnaMatrika[2]
Prav tako posodobite countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

Postavitev inputArray[2] na pravilen položaj v outputArray[]

11. korak: Za i = 1 ,

Nadgradnja izhodnaMatrika[ ŠteviloMatrika[ vhodnaMatrika[1] ] – 1] = vhodnaMatrika[1]
Prav tako posodobite countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

Postavitev inputArray[1] na pravilen položaj v outputArray[]

12. korak: Za i = 0,

Nadgradnja izhodnaMatrika[ ŠteviloMatrika[ vhodnaMatrika[0] ] – 1] = vhodnaMatrika[0]
Prav tako posodobite countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

Postavitev inputArray[0] na pravilen položaj v outputArray[]

Algoritem za razvrščanje štetja:

  • Deklarirajte pomožno matriko countArray[] velikosti max(inputArray[])+1 in ga inicializirajte z 0 .
  • Prečni niz inputArray[] in preslikaj vsak element inputArray[] kot indeks countArray[] array, tj. izvršiti countArray[inputArray[i]]++ za 0 <= i < N .
  • Izračunajte vsoto predpon za vsak indeks matrike inputArray [].
  • Ustvarite niz outputArray[] velikosti n .
  • Prečni niz inputArray[] od konca in posodobitve izhodnaMatrika[ ŠteviloMatrika[ vhodnaMatrika[i] ] – 1] = vhodnaMatrika[i] . Prav tako posodobite countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

Spodaj je izvedba zgornjega algoritma:

Java




import> java.util.Arrays;> public> class> CountSort {> >public> static> int>[] countSort(>int>[] inputArray) {> >int> N = inputArray.length;> >int> M =>0>;> >for> (>int> i =>0>; i M = Math.max(M, inputArray[i]); } int[] countArray = new int[M + 1]; for (int i = 0; i countArray[inputArray[i]]++; } for (int i = 1; i <= M; i++) { countArray[i] += countArray[i - 1]; } int[] outputArray = new int[N]; for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return outputArray; } public static void main(String[] args) { int[] inputArray = {4, 3, 12, 1, 5, 5, 3, 9}; int[] outputArray = countSort(inputArray); for (int i = 0; i System.out.print(outputArray[i] + ' '); } } }>

>

>

C#




using> System;> using> System.Collections.Generic;> class> GFG> {> >static> List<>int>>CountSort(Seznam<>int>>inputArray)> >{> >int> N = inputArray.Count;> >// Finding the maximum element of the array inputArray[].> >int> M = 0;> >for> (>int> i = 0; i M = Math.Max(M, inputArray[i]); // Initializing countArray[] with 0 List countArray = nov seznam (novo int[M + 1]); // Preslikava vsakega elementa inputArray[] kot indeksa // matrike countArray[] za (int i = 0; i countArray[inputArray[i]]++; // Izračun vsote predpone pri vsakem indeksu // matrike countArray [] za (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List outputArray = nov seznam (novo int[N]); for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return outputArray; } // Koda gonilnika static void Main() { // Seznam vhodnega polja inputArray = nov seznam { 4, 3, 12, 1, 5, 5, 3, 9 }; // Seznam izhodne matrike outputArray = CountSort(inputArray); for (int i = 0; i Console.Write(outputArray[i] + ' '); Console.WriteLine(); } }>

>

>

Javascript




function> countSort(inputArray) {> >const N = inputArray.length;> >// Finding the maximum element of inputArray> >let M = 0;> >for> (let i = 0; i M = Math.max(M, inputArray[i]); } // Initializing countArray with 0 const countArray = new Array(M + 1).fill(0); // Mapping each element of inputArray as an index of countArray for (let i = 0; i countArray[inputArray[i]]++; } // Calculating prefix sum at every index of countArray for (let i = 1; i <= M; i++) { countArray[i] += countArray[i - 1]; } // Creating outputArray from countArray const outputArray = new Array(N); for (let i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return outputArray; } // Koda gonilnika const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Razvrščanje vhodne matrike const outputArray = countSort(inputArray); // Tiskanje razvrščene matrike console.log(outputArray.join(' ')); //To kodo je prispeval Utkarsh>

poskusite catch block java

>

>

C++14




#include> using> namespace> std;> vector<>int>>countSort(vektor<>int>>& inputArray)> {> >int> N = inputArray.size();> >// Finding the maximum element of array inputArray[].> >int> M = 0;> >for> (>int> i = 0; i M = max(M, inputArray[i]); // Initializing countArray[] with 0 vector countArray(M + 1, 0); // Preslikava vsakega elementa inputArray[] kot indeksa // matrike countArray[] za (int i = 0; i countArray[inputArray[i]]++; // Izračun vsote predpone pri vsakem indeksu // matrike countArray [] za (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from countArray[] array vector izhodnaMatrika(N); for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return outputArray; } // Koda gonilnika int main() { // Vhodni matrični vektor inputArray = { 4, 3, 12, 1, 5, 5, 3, 9 }; // Vektor izhodne matrike outputArray = countSort(inputArray); for (int i = 0; i cout<< outputArray[i] << ' '; return 0; }>

>

>

Python3




def> count_sort(input_array):> ># Finding the maximum element of input_array.> >M>=> max>(input_array)> ># Initializing count_array with 0> >count_array>=> [>0>]>*> (M>+> 1>)> ># Mapping each element of input_array as an index of count_array> >for> num>in> input_array:> >count_array[num]>+>=> 1> ># Calculating prefix sum at every index of count_array> >for> i>in> range>(>1>, M>+> 1>):> >count_array[i]>+>=> count_array[i>-> 1>]> ># Creating output_array from count_array> >output_array>=> [>0>]>*> len>(input_array)> >for> i>in> range>(>len>(input_array)>-> 1>,>->1>,>->1>):> >output_array[count_array[input_array[i]]>-> 1>]>=> input_array[i]> >count_array[input_array[i]]>->=> 1> >return> output_array> # Driver code> if> __name__>=>=> '__main__'>:> ># Input array> >input_array>=> [>4>,>3>,>12>,>1>,>5>,>5>,>3>,>9>]> ># Output array> >output_array>=> count_sort(input_array)> >for> num>in> output_array:> >print>(num, end>=>' '>)>

>

>

Izhod

1 3 3 4 5 5 9 12>

Analiza kompleksnosti razvrščanja štetja:

  • Časovna zapletenost : O(N+M), kjer je n in M so velikosti inputArray[] in countArray[] oz.
    • Najslabši primer: O(N+M).
    • Povprečni primer: O(N+M).
    • Najboljši primer: O(N+M).
  • Pomožni prostor: O(N+M), kjer je n in M so prostor, ki ga zavzame outputArray[] in countArray[] oz.

Prednost razvrščanja s štetjem:

  • Razvrščanje s štetjem na splošno deluje hitreje kot vsi algoritmi za razvrščanje, ki temeljijo na primerjavi, kot sta razvrščanje z združevanjem in hitro razvrščanje, če je obseg vnosa reda števila vnosov.
  • Razvrstitev s štetjem je enostavno kodirati
  • Razvrščanje štetja je a stabilen algoritem .

Slabost razvrščanja s štetjem:

  • Razvrščanje s štetjem ne deluje pri decimalnih vrednostih.
  • Razvrščanje s štetjem je neučinkovito, če je obseg vrednosti, ki jih je treba razvrstiti, zelo velik.
  • Razvrščanje štetja ni Razvrščanje na mestu algoritem, uporablja dodaten prostor za razvrščanje elementov polja.