logo

TechCodeview

Tellesortering – veiledninger for datastrukturer og algoritmer

Hva er tellesortering?

Tellesortering er en ikke-sammenligningsbasert sorteringsalgoritme som fungerer bra når det er begrenset rekkevidde av inngangsverdier. Det er spesielt effektivt når utvalget av inngangsverdier er lite sammenlignet med antall elementer som skal sorteres. Grunntanken bak Tellesortering er å telle Frekvens av hvert distinkte element i inndatamatrisen og bruk denne informasjonen til å plassere elementene i deres korrekte sorterte posisjoner.

Hvordan fungerer tellesorteringsalgoritmen?

Trinn 1 :



  • Finn ut maksimum element fra den gitte matrisen.

Finne maksimalt element i inputArray[]

Steg 2:

  • Initialiser a countArray[] av lengde maks+1 med alle elementer som 0 . Denne matrisen vil bli brukt til å lagre forekomstene av elementene i inngangsmatrisen.

Initialiser countArray[]



Trinn 3:

  • I countArray[] , lagre tellingen for hvert unike element i inngangsmatrisen ved deres respektive indekser.
  • For eksempel: Antall element 2 i inngangsmatrisen er 2. Så, butikk 2 ved indeks 2 i countArray[] . Tilsvarende antall element 5 i inngangsmatrisen er 1 , derav butikk 1 på indeks 5 i countArray[] .

Oppretthold tellingen av hvert element i countArray[]

Trinn 4:



  • Lagre kumulativ sum eller prefiks sum av elementene i countArray[] ved å gjøre countArray[i] = countArray[i – 1] + countArray[i]. Dette vil hjelpe med å plassere elementene i inngangsmatrisen på riktig indeks i utmatrisen.

Lagre den kumulative summen i countArray[]

Trinn 5:

  • Iterer fra enden av inngangsmatrisen og fordi å krysse innmatrisen fra enden bevarer rekkefølgen av like elementer, noe som til slutt gjør denne sorteringsalgoritmen stabil .
  • Oppdater outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .
  • Oppdater også countArray[ inputArray[i] ] = countArray[ inputArray[i] ] – -.

5

Trinn 6: For i = 6 ,

kunstig intelligens og intelligente agenter

Oppdater outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
Oppdater også countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

Plasser inputArray[6] i riktig posisjon i outputArray[]

Trinn 7: For i = 5 ,

Oppdater outputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
Oppdater også countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

Plasser inputArray[5] i riktig posisjon i outputArray[]

Trinn 8: For i = 4 ,

Oppdater outputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
Oppdater også countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

Plasser inputArray[4] i riktig posisjon i outputArray[]

Trinn 9: For i = 3 ,

Oppdater outputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
Oppdater også countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

Plasser inputArray[3] i riktig posisjon i outputArray[]

Trinn 10: For i = 2 ,

Oppdater outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
Oppdater også countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

Plassering av inputArray[2] i riktig posisjon i outputArray[]

Trinn 11: For i = 1 ,

Oppdater outputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
Oppdater også countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

Plasser inputArray[1] i riktig posisjon i outputArray[]

Trinn 12: For i = 0,

Oppdater outputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
Oppdater også countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

Plasser inputArray[0] i riktig posisjon i outputArray[]

Algoritme for tellesortering:

  • Deklarer en hjelpematrise countArray[] av størrelse max(inputArray[])+1 og initialisere den med 0 .
  • Travers array inputArray[] og kartlegg hvert element av inputArray[] som en indeks på countArray[] array, dvs. utføre countArray[inputArray[i]]++ til 0 <= i < N .
  • Beregn prefikssummen ved hver indeks av matrise inputArray [].
  • Lag en matrise outputArray[] av størrelse N .
  • Travers array inputArray[] fra slutt og oppdatering outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . Oppdater også countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

Nedenfor er implementeringen av algoritmen ovenfor:

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]]--; } returner 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(Liste<>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 = ny liste (ny int[M + 1]); // Kartlegger hvert element i inputArray[] som en indeks // av countArray[] array for (int i = 0; i countArray[inputArray[i]]++; // Beregner prefikssum ved hver indeks // av array countArray [] for (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List outputArray = ny liste (ny int[N]); for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } returner outputArray; } // Driverkode statisk void Main() { // Input array List inputArray = ny liste { 4, 3, 12, 1, 5, 5, 3, 9 }; // Output array List 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]]--; } returner outputArray; } // Driverkode const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Sortering av input-matrisen const outputArray = countSort(inputArray); // Skriver ut den sorterte matrisen console.log(outputArray.join(' ')); //Denne koden er bidratt av Utkarsh>

hvordan returnere array i java 

>

>

C++14




#include> using> namespace> std;> vector<>int>>countSort(vektor<>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); // Kartlegging av hvert element i inputArray[] som en indeks // av countArray[] array for (int i = 0; i countArray[inputArray[i]]++; // Beregner prefikssum ved hver indeks // av 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]]--; } returner outputArray; } // Driverkode int main() { // Input array vector inputArray = { 4, 3, 12, 1, 5, 5, 3, 9 }; // Utgangsmatrisevektor 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>=>' '>)> 

>

>

Produksjon 

1 3 3 4 5 5 9 12>

Kompleksitetsanalyse av tellesort:

  • Tidskompleksitet : O(N+M), hvor N og M er på størrelse med inputArray[] og countArray[] hhv.
    • I verste fall: O(N+M).
    • Gjennomsnittlig-case: O(N+M).
    • Beste tilfelle: O(N+M).
  • Hjelpeplass: O(N+M), hvor N og M er plassen tatt av outputArray[] og countArray[] hhv.

Fordel med tellesortering:

  • Tellesortering utføres generelt raskere enn alle sammenligningsbaserte sorteringsalgoritmer, for eksempel flettesortering og hurtigsortering, hvis inndataområdet er i størrelsesorden antall inndata.
  • Tellesortering er lett å kode
  • Tellesortering er en stabil algoritme .

Ulempen med tellesortering:

  • Å telle sortering fungerer ikke på desimalverdier.
  • Å telle sortering er ineffektivt hvis utvalget av verdier som skal sorteres er svært stort.
  • Å telle sortering er ikke en Sortering på stedet algoritme, den bruker ekstra plass for å sortere array-elementene.