Co to jest liczenie sortowania?
Sortowanie zliczające jest nieoparta na porównaniu algorytm sortowania, który działa dobrze, gdy zakres wartości wejściowych jest ograniczony. Jest to szczególnie efektywne, gdy zakres wartości wejściowych jest mały w porównaniu do liczby elementów do sortowania. Podstawowa idea Sortowanie zliczające jest policzenie częstotliwość każdego odrębnego elementu w tablicy wejściowej i wykorzystaj te informacje do umieszczenia elementów w ich prawidłowych posortowanych pozycjach.
Jak działa algorytm sortowania zliczającego?
Krok 1 :
- Dowiedz się maksymalny element z podanej tablicy.
Krok 2:
- Zainicjuj a liczbaTablica[] długości maks.+1 ze wszystkimi elementami jak 0 . Tablica ta będzie używana do przechowywania wystąpień elementów tablicy wejściowej.
Krok 3:
- w liczbaTablica[] , przechowuj liczbę każdego unikalnego elementu tablicy wejściowej w odpowiednich indeksach.
- Na przykład: Liczba elementów 2 w tablicy wejściowej jest 2. Więc sklep 2 w indeksie 2 w liczbaTablica[] . Podobnie liczba elementów 5 w tablicy wejściowej jest 1 , stąd sklep 1 w indeksie 5 w liczbaTablica[] .
Krok 4:
- Przechowuj suma skumulowana Lub suma przedrostków z elementów liczbaTablica[] wykonując countArray[i] = countArray[i – 1] + countArray[i]. Pomoże to w umieszczeniu elementów tablicy wejściowej pod właściwym indeksem tablicy wyjściowej.
Krok 5:
- Iteruj od końca tablicy wejściowej, a ponieważ przejście przez tablicę wejściową od końca zachowuje kolejność równych elementów, co ostatecznie tworzy ten algorytm sortowania stabilny .
- Aktualizacja tablica wyjściowa [liczba tablic [ tablica wejściowa [i] ] – 1] = tablica wejściowa [i] .
- Aktualizuj także liczbaArray[tablica wejściowa[i]] = countArray[inputArray[i] ] – -.
Krok 6: Dla i = 6 ,
co to jest mapa skrótu Java
Aktualizacja tablica wyjściowa [liczba tablic [ tablica wejściowa [6] ] – 1] = tablica wejściowa [6]
Aktualizuj także countArray[inputArray[6] ] = countArray[inputArray[6] ]- –
Krok 7: Dla i = 5 ,
Aktualizacja tablica wyjściowa [liczba tablic [ tablica wejściowa [5] ] – 1] = tablica wejściowa [5]
Aktualizuj także countArray[inputArray[5] ] = countArray[inputArray[5] ]- –
Krok 8: Dla i = 4 ,
Aktualizacja tablica wyjściowa [liczba tablic [ tablica wejściowa [4] ] – 1] = tablica wejściowa [4]
Aktualizuj także countArray[inputArray[4] ] = countArray[inputArray[4] ]- –
Krok 9: Dla i = 3 ,
Aktualizacja tablica wyjściowa [liczba tablic [ tablica wejściowa [3] ] – 1] = tablica wejściowa [3]
Aktualizuj także countArray[inputArray[3] ] = countArray[inputArray[3] ]- –
Krok 10: Dla i = 2 ,
Aktualizacja tablica wyjściowa [liczba tablic [ tablica wejściowa [2] ] – 1] = tablica wejściowa [2]
Aktualizuj także countArray[inputArray[2] ] = countArray[inputArray[2] ]- –
Krok 11: Dla i = 1 ,
Aktualizacja tablica wyjściowa [liczba tablic [ tablica wejściowa [1] ] – 1] = tablica wejściowa [1]
Aktualizuj także countArray[inputArray[1] ] = countArray[inputArray[1] ]- –
Krok 12: Dla i = 0,
Aktualizacja tablica wyjściowa [liczba tablic [ tablica wejściowa [0] ] – 1] = tablica wejściowa [0]
Aktualizuj także countArray[inputArray[0] ] = countArray[inputArray[0] ]- –
Algorytm sortowania zliczającego:
- Zadeklaruj tablicę pomocniczą liczbaTablica[] wielkościowy max(tablica wejściowa[])+1 i zainicjuj go za pomocą 0 .
- Układ poprzeczny tablica wejściowa[] i zmapuj każdy element tablica wejściowa[] jako indeks liczbaTablica[] array, czyli wykonaj liczbaTablica[Tablicawejściowa[i]]++ Do 0 <= ja < N .
- Oblicz sumę prefiksów przy każdym indeksie tablicy tablica wejściowa [].
- Utwórz tablicę tablica wyjściowa[] wielkościowy N .
- Układ poprzeczny tablica wejściowa[] od końca i zaktualizuj tablica wyjściowa [liczba tablic [ tablica wejściowa [i] ] – 1] = tablica wejściowa [i] . Aktualizuj także countArray[inputArray[i] ] = countArray[inputArray[i] ]- – .
Poniżej implementacja powyższego algorytmu:
Jawa
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]]--; } zwróć tablicę wyjściową; } 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(Lista<> int> >tablica wejściowa)> > {> > 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]]--; } zwróć tablicę wyjściową; } // Kod sterownika const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Sortowanie tablicy wejściowej const OutputArray = countSort(inputArray); // Drukowanie posortowanej tablicy console.log(outputArray.join(' ')); //Ten kod jest dziełem Utkarsha> |
konwersja obiektu na ciąg
>
>
C++14
#include> using> namespace> std;> vector<> int> >liczbaSortuj(wektor<> int> >& tablica wejściowa)> {> > 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> => ' '> )> |
>
>Wyjście
1 3 3 4 5 5 9 12>
Analiza złożoności sortowania zliczającego:
- Złożoność czasu : O(N+M), gdzie N I M są wielkości tablica wejściowa[] I liczbaTablica[] odpowiednio.
- Najgorszy przypadek: O(N+M).
- Przypadek średni: O(N+M).
- Najlepszy przypadek: O(N+M).
- Przestrzeń pomocnicza: O(N+M), gdzie N I M to przestrzeń zajmowana przez tablica wyjściowa[] I liczbaTablica[] odpowiednio.
Zaleta sortowania zliczającego:
- Sortowanie zliczające zazwyczaj działa szybciej niż wszystkie algorytmy sortowania oparte na porównaniach, takie jak sortowanie przez scalanie i sortowanie szybkie, jeśli zakres danych wejściowych jest rzędu liczby danych wejściowych.
- Sortowanie zliczające jest łatwe do zakodowania
- Sortowanie zliczające to a stabilny algorytm .
Wady sortowania zliczającego:
- Sortowanie zliczające nie działa w przypadku wartości dziesiętnych.
- Sortowanie zliczające jest nieefektywne, jeśli zakres wartości do sortowania jest bardzo duży.
- Sortowanie zliczające nie jest Sortowanie na miejscu algorytm, wykorzystuje dodatkową przestrzeń do sortowania elementów tablicy.