logo

TechCodeview

Tellen Sorteren - Tutorials voor gegevensstructuren en algoritmen

Wat is telsortering?

Tellen Sorteren is een niet op vergelijking gebaseerd sorteeralgoritme dat goed werkt als er een beperkt bereik aan invoerwaarden is. Het is bijzonder efficiënt wanneer het bereik van de invoerwaarden klein is in vergelijking met het aantal te sorteren elementen. Het basisidee erachter Tellen Sorteren is het tellen van de frequentie van elk afzonderlijk element in de invoerarray en gebruik die informatie om de elementen op de juiste gesorteerde posities te plaatsen.

Hoe werkt het tel-sorteeralgoritme?

Stap 1 :



  • Ontdek de maximaal element uit de gegeven array.

Het maximale element zoeken in inputArray[]

Stap 2:

  • Initialiseer een telArray[] van lengte maximaal+1 met alle elementen als 0 . Deze array wordt gebruikt voor het opslaan van de voorkomens van de elementen van de invoerarray.

Initialiseer countArray[]



Stap 3:

  • In de telArray[] , sla de telling van elk uniek element van de invoerarray op in hun respectieve indices.
  • Bijvoorbeeld: Het aantal elementen 2 in de invoerarray is 2. Opslaan dus 2 bij index 2 in de telArray[] . Hetzelfde geldt voor het aantal elementen 5 in de invoerarray is 1 , vandaar opslaan 1 bij index 5 in de telArray[] .

Houd de telling bij van elk element in countArray[]

Stap 4:



  • Bewaar de cumulatieve som of voorvoegsel som van de elementen van de telArray[] door te doen countArray[i] = countArray[i – 1] + countArray[i]. Dit zal helpen bij het plaatsen van de elementen van de invoerarray op de juiste index in de uitvoerarray.

Bewaar de cumulatieve som in countArray[]

Stap 5:

  • Itereer vanaf het einde van de invoerarray en omdat het doorlopen van de invoerarray vanaf het einde de volgorde van gelijke elementen behoudt, waardoor dit sorteeralgoritme uiteindelijk stal .
  • Update outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .
  • Ook bijwerken telArray[invoerArray[i] ] = telArray[invoerArray[i] ] – -.

5

Stap 6: Voor ik = 6 ,

np.random.rand

Update outputArray[ telArray[ inputArray[6] ] – 1] = inputArray[6]
Ook bijwerken countArray[invoerArray[6] ] = countArray[invoerArray[6] ]- –

InputArray[6] op de juiste positie in outputArray[] plaatsen

Stap 7: Voor ik = 5 ,

Update outputArray[ telArray[ inputArray[5] ] – 1] = inputArray[5]
Ook bijwerken countArray[invoerArray[5] ] = countArray[invoerArray[5] ]- –

InputArray[5] op de juiste positie in outputArray[] plaatsen

Stap 8: Voor ik = 4 ,

Update outputArray[ telArray[ inputArray[4] ] – 1] = inputArray[4]
Ook bijwerken countArray[invoerArray[4] ] = countArray[invoerArray[4] ]- –

InputArray[4] op de juiste positie in outputArray[] plaatsen

Stap 9: Voor ik = 3 ,

Update outputArray[ telArray[ inputArray[3] ] – 1] = inputArray[3]
Ook bijwerken countArray[invoerArray[3] ] = countArray[invoerArray[3] ]- –

InputArray[3] op de juiste positie in outputArray[] plaatsen

Stap 10: Voor ik = 2 ,

Update outputArray[ telArray[ inputArray[2] ] – 1] = inputArray[2]
Ook bijwerken countArray[invoerArray[2] ] = countArray[invoerArray[2] ]- –

InputArray[2] op de juiste positie in outputArray[] plaatsen

Stap 11: Voor ik = 1 ,

Update outputArray[ telArray[ inputArray[1] ] – 1] = inputArray[1]
Ook bijwerken countArray[invoerArray[1] ] = countArray[invoerArray[1] ]- –

InputArray[1] op de juiste positie in outputArray[] plaatsen

Stap 12: Voor ik = 0,

Update outputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
Ook bijwerken countArray[invoerArray[0] ] = countArray[invoerArray[0] ]- –

InputArray[0] op de juiste positie in outputArray[] plaatsen

Sorteeralgoritme tellen:

  • Declareer een hulparray telArray[] van grootte max(invoerArray[])+1 en initialiseer het met 0 .
  • Doorkruis array invoerArray[] en breng elk element in kaart invoerArray[] als index van telArray[] array, dat wil zeggen, uitvoeren countArray[invoerArray[i]]++ voor 0 <= ik < N .
  • Bereken de prefixsom bij elke index van de array invoerArray [].
  • Maak een array uitvoerArray[] van grootte N .
  • Doorkruis array invoerArray[] vanaf het einde en update outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . Ook bijwerken countArray[invoerArray[i] ] = countArray[invoerArray[i] ]- – .

Hieronder ziet u de implementatie van het bovenstaande algoritme:

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; ik--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[invoerArray[i]]--; } retourneer 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>>TelSort(Lijst<>int>>invoerArray)> >{> >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 = nieuwe lijst (nieuwe int[M + 1]); // Elk element van inputArray[] in kaart brengen als een index // van countArray[] array voor (int i = 0; i countArray[inputArray[i]]++; // Voorvoegselsom berekenen bij elke index // van array countArray [] voor (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List outputArray = nieuwe lijst (nieuwe int[N]); for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[invoerArray[i]]--; } retourneer outputArray; } // Stuurprogrammacode static void Main() {// Invoerarraylijst inputArray = nieuwe lijst { 4, 3, 12, 1, 5, 5, 3, 9 }; // Uitvoerarraylijst outputArray = TelSort(invoerArray); 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; ik--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[invoerArray[i]]--; } retourneer outputArray; } // Stuurprogrammacode const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // De invoerarray sorteren const outputArray = countSort(inputArray); // De gesorteerde array console.log afdrukken (outputArray.join(' ')); //Deze code is bijgedragen door Utkarsh>

Java-filterstream 

>

>

C++14




#include> using> namespace> std;> vector<>int>>countSort(vector<>int>>&invoerArray)> {> >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); // Elk element van inputArray[] in kaart brengen als een index // van countArray[] array voor (int i = 0; i countArray[inputArray[i]]++; // Voorvoegselsom berekenen bij elke index // van array countArray [] voor (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from countArray[] array vector uitvoerArray(N); for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[invoerArray[i]]--; } retourneer outputArray; } // Stuurprogrammacode int main() {// Invoerarrayvector invoerArray = { 4, 3, 12, 1, 5, 5, 3, 9 }; // Uitvoerarrayvector outputArray = countSort(inputArray); voor (int i = 0; ik 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>=>' '>)> 

>

>

Uitvoer 

1 3 3 4 5 5 9 12>

Complexiteitsanalyse van telsortering:

  • Tijdcomplexiteit : O(N+M), waarbij N En M zijn de grootte van invoerArray[] En telArray[] respectievelijk.
    • In het ergste geval: O(N+M).
    • Gemiddeld geval: O(N+M).
    • In het beste geval: O(N+M).
  • Hulpruimte: O(N+M), waarbij N En M zijn de ruimte die wordt ingenomen uitvoerArray[] En telArray[] respectievelijk.

Voordeel van tellen sorteren:

  • Telsortering werkt over het algemeen sneller dan alle op vergelijkingen gebaseerde sorteeralgoritmen, zoals merge sort en quicksort, als het invoerbereik in de orde van grootte van het aantal invoer ligt.
  • Telsortering is eenvoudig te coderen
  • Telsoort is een stabiel algoritme .

Nadeel van tellen sorteren:

  • Telsortering werkt niet op decimale waarden.
  • Het tellen van sorteringen is inefficiënt als het bereik van de te sorteren waarden erg groot is.
  • Sorteren is geen Sortering ter plaatse algoritme, het gebruikt extra ruimte voor het sorteren van de array-elementen.