logo

TechCodeview

Sortowanie zliczające – samouczki dotyczące struktur danych i algorytmów

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.

Znajdowanie maksymalnego elementu w inputArray[]

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.

Zainicjuj licznikArray[]



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[] .

Zachowaj liczbę każdego elementu w countArray[]

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.

Przechowuj skumulowaną sumę w countArray[]

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] ] – -.

5

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] ]- –

Umieszczenie inputArray[6] we właściwej pozycji w OutputArray[]

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] ]- –

Umieszczenie inputArray[5] we właściwej pozycji w OutputArray[]

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] ]- –

Umieszczenie inputArray[4] we właściwej pozycji w OutputArray[]

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] ]- –

Umieszczenie inputArray[3] we właściwej pozycji w OutputArray[]

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] ]- –

Umieszczenie inputArray[2] we właściwej pozycji w OutputArray[]

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] ]- –

Umieszczenie inputArray[1] we właściwej pozycji w OutputArray[]

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] ]- –

Umieszczenie inputArray[0] we właściwej pozycji w OutputArray[]

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 countArray = nowa lista (nowy int[M + 1]); // Mapowanie każdego elementu inputArray[] jako indeks // tablicy countArray[] dla (int i = 0; i countArray[inputArray[i]]++; // Obliczanie sumy przedrostków przy każdym indeksie // tablicy countArray [] for (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List OutputArray = nowa lista (nowy int[N]); for (int i = N - 1; i>= 0; i--) { OutputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } zwróć tablicę wyjściową; } // Kod sterownika static void Main() { // Lista tablic wejściowych inputArray = nowa lista {4, 3, 12, 1, 5, 5, 3, 9}; // Lista tablic wyjściowych 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]]--; } 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 liczbaArray(M + 1, 0); // Mapowanie każdego elementu inputArray[] jako indeks // tablicy countArray[] dla (int i = 0; i countArray[inputArray[i]]++; // Obliczanie sumy przedrostków przy każdym indeksie // tablicy countArray [] for (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from countArray[] array vector tablica wyjściowa(N); for (int i = N - 1; i>= 0; i--) { OutputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } zwróć tablicę wyjściową; } // Kod sterownika int main() { // Wprowadź wektor tablicy tablica wejściowa = { 4, 3, 12, 1, 5, 5, 3, 9 }; //Wektor tablicy wyjściowej tablica wyjściowa = liczba sortowania (tablica wejściowa); 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>=>' '>)> 

>

>

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.