SORTARE DE NUMĂRARE - STRUCTURI DE DATE ȘI TUTORIALE PENTRU ALGORITMI - TECHCODEVIEW.COM

Ce este Counting Sort?

Sortare de numărare este o nebazat pe comparație algoritm de sortare care funcționează bine atunci când există o gamă limitată de valori de intrare. Este deosebit de eficient atunci când intervalul de valori de intrare este mic în comparație cu numărul de elemente care trebuie sortate. Ideea de bază din spate Sortare de numărare este de a număra frecvență a fiecărui element distinct din matricea de intrare și utilizați acele informații pentru a plasa elementele în pozițiile lor corecte sortate.

Cum funcționează algoritmul de sortare de numărare?

Pasul 1 :

Aflați maxim element din tabloul dat.

Găsirea elementului maxim în inputArray[]

Pasul 2:

Inițializați a countArray[] de lungime max+1 cu toate elementele ca 0 . Această matrice va fi folosită pentru stocarea aparițiilor elementelor matricei de intrare.

Inițializați countArray[]

Pasul 3:

În countArray[] , stochează numărul fiecărui element unic al matricei de intrare la indicii respectivi.
De exemplu: Numărul de elemente 2 în matricea de intrare este 2. Deci, magazin 2 la index 2 în countArray[] . În mod similar, numărul de elemente 5 în matricea de intrare este 1 , deci magazin 1 la index 5 în countArray[] .

Menține numărul fiecărui element din countArray[]

Pasul 4:

Depozitați suma cumulata sau suma prefixului a elementelor din countArray[] facand countArray[i] = countArray[i – 1] + countArray[i]. Acest lucru va ajuta la plasarea elementelor matricei de intrare la indexul corect în matricea de ieșire.

Stocați suma cumulativă în countArray[]

Pasul 5:

Iterați de la sfârșitul matricei de intrare și deoarece parcurgerea matricei de intrare de la sfârșit păstrează ordinea elementelor egale, ceea ce face în cele din urmă acest algoritm de sortare grajd .

Actualizați outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .

De asemenea, actualizați countArray[ inputArray[i] ] = countArray[ inputArray[i] ] – -.

Pasul 6: Pentru i = 6 ,

ce este o interfață

Actualizați outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
De asemenea, actualizați countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

Plasarea inputArray[6] în poziția corectă în outputArray[]

Pasul 7: Pentru i = 5 ,

Actualizați outputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
De asemenea, actualizați countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

Plasarea inputArray[5] în poziția corectă în outputArray[]

Pasul 8: Pentru i = 4 ,

Actualizați outputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
De asemenea, actualizați countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

Plasarea inputArray[4] în poziția corectă în outputArray[]

Pasul 9: Pentru i = 3 ,

Actualizați outputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
De asemenea, actualizați countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

Plasarea inputArray[3] în poziția corectă în outputArray[]

Pasul 10: Pentru i = 2 ,

Actualizați outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
De asemenea, actualizați countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

Plasarea inputArray[2] în poziția corectă în outputArray[]

Pasul 11: Pentru i = 1 ,

Actualizați outputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
De asemenea, actualizați countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

Plasarea inputArray[1] în poziția corectă în outputArray[]

Pasul 12: Pentru i = 0,

Actualizați outputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
De asemenea, actualizați countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

Plasarea inputArray[0] în poziția corectă în outputArray[]

Algoritm de sortare de numărare:

Declarați o matrice auxiliară countArray[] de mărime max(inputArray[])+1 și inițializați-l cu 0 .
Matrice transversală inputArray[] și cartografiază fiecare element al inputArray[] ca indice al countArray[] matrice, adică execută countArray[inputArray[i]]++ pentru 0 <= i < N .
Calculați suma prefixelor la fiecare index al matricei inputArray [].
Creați o matrice outputArray[] de mărime N .
Matrice transversală inputArray[] de la sfârșit și actualizare outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . De asemenea, actualizați countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

Mai jos este implementarea algoritmului de mai sus:

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]]--;  } returnează outputArray;  } public static void main(String[] args) { int[] inputArray = {4, 3, 12, 1, 5, 5, 3, 9};  int[] outputArray = countSort(inputArray);  pentru (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 = listă nouă (nou int[M + 1]);  // Maparea fiecărui element al inputArray[] ca index // al matricei countArray[] pentru (int i = 0; i countArray[inputArray[i]]++; // Calcularea sumei prefixelor la fiecare index // al matricei countArray [] pentru (int i = 1; i<= M; i++)  countArray[i] += countArray[i - 1];  // Creating outputArray[] from the countArray[] array  List outputArray = listă nouă (nou int[N]);  pentru (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i];  countArray[inputArray[i]]--;  } returnează outputArray;  } // Cod driver static void Main() { // Lista matrice de intrare inputArray = listă nouă { 4, 3, 12, 1, 5, 5, 3, 9 };  // Listă matrice de ieșire outputArray = CountSort(inputArray);  pentru (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]]--;  } returnează outputArray; } // Cod driver const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Sortarea matricei de intrare const outputArray = countSort(inputArray); // Tipărirea matricei sortate console.log(outputArray.join(' ')); //Acest cod este contribuit de Utkarsh>>>

java convertește char în int

> 
    
   
      
  
     
      
     
    
 
     #include> using> namespace> std;> vector<>int>>countSort(vector<>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);  // Maparea fiecărui element al inputArray[] ca index // al matricei countArray[] pentru (int i = 0; i countArray[inputArray[i]]++; // Calcularea sumei prefixelor la fiecare index // al matricei countArray [] pentru (int i = 1; i<= M; i++)  countArray[i] += countArray[i - 1];  // Creating outputArray[] from countArray[] array  vector outputArray(N);  pentru (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i];  countArray[inputArray[i]]--;  } returnează outputArray; } // Cod driver int main() { // Vector matrice de intrare inputArray = { 4, 3, 12, 1, 5, 5, 3, 9 };  // Vector matrice de ieșire outputArray = countSort(inputArray);  pentru (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>=>' '>)>  
 
 
 
    
 >
 
    
 >
 
  Ieșire  
 1 3 3 4 5 5 9 12>
 Analiza complexității sortării de numărare:
      Complexitatea timpului    : O(N+M), unde    N    și    M    sunt de dimensiunea    inputArray[]    și    countArray[]    respectiv.  Cel mai rău caz: O(N+M).
 Caz mediu: O(N+M).
 Cel mai bun caz: O(N+M).
 
 
     Spațiu auxiliar:    O(N+M), unde    N    și    M    sunt spatiul ocupat de    outputArray[]    și    countArray[]    respectiv.
 
 Avantajul sortării de numărare:
  Sortarea prin numărare funcționează în general mai rapid decât toți algoritmii de sortare bazați pe comparație, cum ar fi sortarea prin îmbinare și sortarea rapidă, dacă intervalul de intrare este de ordinul numărului de intrări.
 Sortarea numărării este ușor de codificat
 Sortarea de numărare este a    algoritm stabil    .
 
 Dezavantajul sortării de numărare:
  Sortarea de numărare nu funcționează pe valori zecimale.
 Sortarea de numărare este ineficientă dacă intervalul de valori care trebuie sortat este foarte mare.
 Numărarea sortării nu este o    Sortare in loc    algoritm, folosește spațiu suplimentar pentru sortarea elementelor matricei.

TechCodeview

Counting Sort – Structuri de date și tutoriale de algoritmi

Ce este Counting Sort?

Cum funcționează algoritmul de sortare de numărare?

Algoritm de sortare de numărare:

Java

C#

Javascript

Python3

Analiza complexității sortării de numărare:

Avantajul sortării de numărare:

Dezavantajul sortării de numărare: