logo

TechCodeview

Ordinamento dei conteggi: tutorial su strutture dati e algoritmi

Cos'è l'ordinamento conteggiato?

Conteggio dell'ordinamento è un non basato sul confronto algoritmo di ordinamento che funziona bene quando l'intervallo di valori di input è limitato. È particolarmente efficiente quando l'intervallo dei valori di input è piccolo rispetto al numero di elementi da ordinare. L'idea di base dietro Conteggio dell'ordinamento è contare il frequenza di ciascun elemento distinto nell'array di input e utilizzare tali informazioni per posizionare gli elementi nelle posizioni ordinate corrette.

Come funziona l'algoritmo di ordinamento del conteggio?

Passo 1 :



  • Scopri il massimo elemento dall'array specificato.

Trovare l'elemento massimo in inputArray[]

Passo 2:

  • Inizializzare a conteggioArray[] di lunghezza massimo+1 con tutti gli elementi come 0 . Questo array verrà utilizzato per memorizzare le occorrenze degli elementi dell'array di input.

Inizializza countArray[]



Passaggio 3:

  • Nel conteggioArray[] , memorizza il conteggio di ciascun elemento univoco dell'array di input nei rispettivi indici.
  • Per esempio: Il conteggio degli elementi 2 nell'array di input è 2. Quindi, negozio 2 all'indice 2 nel conteggioArray[] . Allo stesso modo, il conteggio di element 5 nell'array di input è 1 , quindi memorizzare 1 all'indice 5 nel conteggioArray[] .

Mantieni il conteggio di ogni elemento in countArray[]

Passaggio 4:



  • Conservare il somma cumulativa O somma del prefisso degli elementi del conteggioArray[] facendo countArray[i] = countArray[i – 1] + countArray[i]. Ciò aiuterà a posizionare gli elementi dell'array di input nell'indice corretto nell'array di output.

Memorizza la somma cumulativa in countArray[]

Passaggio 5:

  • Itera dalla fine dell'array di input e poiché l'attraversamento dell'array di input dalla fine preserva l'ordine degli elementi uguali, il che alla fine rende questo algoritmo di ordinamento stabile .
  • Aggiornamento outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .
  • Inoltre, aggiorna conteggioArray[ inputArray[i] ] = countArray[ inputArray[i] ] – -.

5

Passaggio 6: Per i = 6 ,

10 di 1 milione

Aggiornamento outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
Inoltre, aggiorna countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

Posizionando inputArray[6] nella posizione corretta in outputArray[]

Passaggio 7: Per i = 5 ,

Aggiornamento outputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
Inoltre, aggiorna countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

Posizionando inputArray[5] nella posizione corretta in outputArray[]

Passaggio 8: Per i = 4 ,

Aggiornamento outputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
Inoltre, aggiorna countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

Posizionando inputArray[4] nella posizione corretta in outputArray[]

Passaggio 9: Per i = 3 ,

Aggiornamento outputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
Inoltre, aggiorna countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

Posizionando inputArray[3] nella posizione corretta in outputArray[]

Passaggio 10: Per i = 2 ,

Aggiornamento outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
Inoltre, aggiorna countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

Posizionando inputArray[2] nella posizione corretta in outputArray[]

Passaggio 11: Per i = 1 ,

Aggiornamento outputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
Inoltre, aggiorna countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

Posizionando inputArray[1] nella posizione corretta in outputArray[]

Passaggio 12: Per i = 0,

Aggiornamento outputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
Inoltre, aggiorna countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

Posizionando inputArray[0] nella posizione corretta in outputArray[]

Algoritmo di ordinamento del conteggio:

  • Dichiarare un array ausiliario conteggioArray[] di dimensione max(inputArray[])+1 e inizializzarlo con 0 .
  • Matrice trasversale inputArray[] e mappare ogni elemento di inputArray[] come indice di conteggioArray[] array, cioè eseguire countArray[inputArray[i]]++ per 0 <= io < N .
  • Calcola la somma dei prefissi su ogni indice dell'array inputArray [].
  • Crea una matrice outputArray[] di dimensione N .
  • Matrice trasversale inputArray[] dalla fine e aggiornamento outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . Inoltre, aggiorna countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

Di seguito è riportata l'implementazione dell'algoritmo di cui sopra:

Giava




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]]--; } restituisce 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(Lista<>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 = nuova lista (nuovo int[M + 1]); // Mappatura di ciascun elemento di inputArray[] come indice // dell'array countArray[] for (int i = 0; i countArray[inputArray[i]]++; // Calcolo della somma dei prefissi su ogni indice // dell'array countArray [] for (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List outputArray = nuova lista (nuovo int[N]); for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } restituisce outputArray; } // Codice driver static void Main() { // Elenco array di input inputArray = nuova lista { 4, 3, 12, 1, 5, 5, 3, 9 }; // Elenco degli array di output 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]]--; } restituisce outputArray; } // Codice driver const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Ordinamento dell'array di input const outputArray = countSort(inputArray); // Stampa l'array ordinato console.log(outputArray.join(' ')); //Questo codice è fornito da Utkarsh>

come leggere dal file CSV in Java 

>

>

C++14




#include> using> namespace> std;> vector<>int>>countSort(vettore<>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 conteggioArray(M + 1, 0); // Mappatura di ciascun elemento di inputArray[] come indice // dell'array countArray[] for (int i = 0; i countArray[inputArray[i]]++; // Calcolo della somma dei prefissi su ogni indice // dell'array countArray [] for (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from countArray[] array vector outputArray(N); for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } restituisce outputArray; } // Codice driver int main() { // Vettore dell'array di input inputArray = { 4, 3, 12, 1, 5, 5, 3, 9 }; // Vettore dell'array di output 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>=>' '>)> 

>

>

Produzione 

1 3 3 4 5 5 9 12>

Analisi della complessità dell'ordinamento di conteggio:

  • Complessità temporale : O(N+M), dove N E M hanno le dimensioni di inputArray[] E conteggioArray[] rispettivamente.
    • Caso peggiore: O(N+M).
    • Caso medio: O(N+M).
    • Caso migliore: O(N+M).
  • Spazio ausiliario: O(N+M), dove N E M sono lo spazio occupato da outputArray[] E conteggioArray[] rispettivamente.

Vantaggio dell'ordinamento del conteggio:

  • L'ordinamento con conteggio generalmente viene eseguito più velocemente di tutti gli algoritmi di ordinamento basati sul confronto, come Merge Sort e Quicksort, se l'intervallo di input è dell'ordine del numero di input.
  • L'ordinamento dei conteggi è facile da codificare
  • L'ordinamento di conteggio è a algoritmo stabile .

Svantaggio dell'ordinamento del conteggio:

  • L'ordinamento dei conteggi non funziona sui valori decimali.
  • L'ordinamento del conteggio è inefficiente se l'intervallo di valori da ordinare è molto ampio.
  • L'ordinamento del conteggio non è un Ordinamento sul posto algoritmo, utilizza spazio aggiuntivo per ordinare gli elementi dell'array.