Co je třídění počítání?
Počítání Řadit je nezaložené na srovnání třídicí algoritmus, který funguje dobře, když je omezený rozsah vstupních hodnot. Je zvláště efektivní, když je rozsah vstupních hodnot malý ve srovnání s počtem prvků, které mají být seřazeny. Základní myšlenka Počítání Řadit je počítat frekvence každého odlišného prvku ve vstupním poli a použít tyto informace k umístění prvků na jejich správné seřazené pozice.
Jak funguje algoritmus řazení počítání?
Krok 1 :
- Zjistěte maximum prvek z daného pole.
Krok 2:
- Inicializovat a countArray[] délky max+1 se všemi prvky jako 0 . Toto pole bude použito pro uložení výskytů prvků vstupního pole.
Krok 3:
- V countArray[] , uložte počet každého jedinečného prvku vstupního pole do jejich příslušných indexů.
- Například: Počet prvků 2 ve vstupním poli je 2. Takže skladujte 2 na indexu 2 v countArray[] . Podobně počet prvků 5 ve vstupním poli je 1 , tedy obchod 1 na indexu 5 v countArray[] .
Krok 4:
- Uložte kumulativní součet nebo předčíslí součet z prvků countArray[] tím, že dělá countArray[i] = countArray[i – 1] + countArray[i]. To pomůže umístit prvky vstupního pole na správný index ve výstupním poli.
Krok 5:
- Iterujte od konce vstupního pole a protože procházení vstupního pole od konce zachovává pořadí stejných prvků, což nakonec způsobí tento třídicí algoritmus stabilní .
- Aktualizace outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .
- Také aktualizujte countArray[ inputArray[i] ] = countArray[ inputArray[i] ] – –.
Krok 6: Pro i = 6 ,
prologový jazyk
Aktualizace outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
Také aktualizujte countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –
Krok 7: Pro i = 5 ,
Aktualizace outputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
Také aktualizujte countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –
Krok 8: Pro i = 4 ,
Aktualizace outputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
Také aktualizujte countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –
Krok 9: Pro i = 3 ,
Aktualizace outputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
Také aktualizujte countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –
Krok 10: Pro i = 2 ,
Aktualizace outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
Také aktualizujte countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –
Krok 11: Pro i = 1 ,
Aktualizace outputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
Také aktualizujte countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –
Krok 12: pro i = 0,
Aktualizace outputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
Také aktualizujte countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –
Algoritmus řazení počítání:
- Deklarujte pomocné pole countArray[] velikosti max(inputArray[])+1 a inicializujte jej pomocí 0 .
- Traverzové pole inputArray[] a mapovat každý prvek inputArray[] jako index countArray[] pole, tj. spustit countArray[inputArray[i]]++ pro 0 <= i < N .
- Vypočítejte součet prefixů pro každý index pole inputArray [].
- Vytvořte pole outputArray[] velikosti N .
- Traverzové pole inputArray[] od konce a aktualizace outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . Také aktualizujte countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .
Níže je uvedena implementace výše uvedeného algoritmu:
Jáva
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 |
>
>
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; } // Kód ovladače const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Třídění vstupního pole const outputArray = countSort(inputArray); // Tisk seřazeného pole console.log(outputArray.join(' ')); //Tento kód přispěl Utkarsh> |
převést z char na int 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 |
>
>
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> => )> |
>
>Výstup
1 3 3 4 5 5 9 12>
Analýza složitosti řazení počítání:
- Časová složitost : O(N+M), kde N a M jsou velikosti inputArray[] a countArray[] respektive.
- Nejhorší případ: O(N+M).
- Průměrný případ: O(N+M).
- Nejlepší případ: O(N+M).
- Pomocný prostor: O(N+M), kde N a M zabírají prostor outputArray[] a countArray[] respektive.
Výhoda řazení počítání:
- Počítání třídění obecně funguje rychleji než všechny třídicí algoritmy založené na porovnání, jako je slučovací třídění a rychlé třídění, pokud je rozsah vstupu řádově číslo vstupu.
- Počítání třídění je snadné kódovat
- Druh počítání je a stabilní algoritmus .
Nevýhoda řazení počítání:
- Třídění počítání nefunguje s desetinnými hodnotami.
- Třídění počítání je neefektivní, pokud je rozsah hodnot, které mají být seřazeny, velmi velký.
- Počítání řazení není Třídění na místě algoritmu, Využívá extra prostor pro třídění prvků pole.