logo

TechCodeview

Tællesortering – Vejledninger om datastrukturer og algoritmer

Hvad er tællesortering?

Tællesort er en ikke-sammenligningsbaseret sorteringsalgoritme, der fungerer godt, når der er begrænset række af inputværdier. Det er særligt effektivt, når intervallet af inputværdier er lille sammenlignet med antallet af elementer, der skal sorteres. Grundtanken bag Tællesort er at tælle frekvens af hvert enkelt element i input-arrayet og bruge denne information til at placere elementerne i deres korrekte sorterede positioner.

Hvordan fungerer tællesorteringsalgoritmen?

Trin 1 :



  • Find ud af maksimum element fra det givne array.

Finder det maksimale element i inputArray[]

Trin 2:

  • Initialiser a countArray[] af længde max+1 med alle elementer som 0 . Dette array vil blive brugt til at gemme forekomsterne af elementerne i input-arrayet.

Initialiser countArray[]



Trin 3:

  • I den countArray[] , gemmer antallet af hvert unikt element i input-arrayet ved deres respektive indekser.
  • For eksempel: Antallet af element 2 i input-arrayet er 2. Så, gemme 2 ved indeks 2 i countArray[] . På samme måde, antallet af element 5 i input-arrayet er 1 , derfor butik 1 ved indeks 5 i countArray[] .

Oprethold antallet af hvert element i countArray[]

Trin 4:



  • Opbevar kumulativ sum eller præfiks sum af elementerne i countArray[] ved at gøre countArray[i] = countArray[i – 1] + countArray[i]. Dette vil hjælpe med at placere elementerne i input-arrayet ved det korrekte indeks i output-arrayet.

Gem den kumulative sum i countArray[]

Trin 5:

  • Iterér fra slutningen af ​​input-arrayet, og fordi krydsning af input-array fra ende bevarer rækkefølgen af ​​lige elementer, hvilket til sidst gør denne sorteringsalgoritme stabil .
  • Opdatering outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .
  • Opdater også countArray[ inputArray[i] ] = countArray[ inputArray[i] ] – -.

5

Trin 6: For i = 6 ,

kunstig intelligens og intelligente agenter

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

Placering af inputArray[6] på den korrekte position i outputArray[]

Trin 7: For i = 5 ,

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

Anbringelse af inputArray[5] på den korrekte position i outputArray[]

Trin 8: For i = 4 ,

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

Placering af inputArray[4] på den korrekte position i outputArray[]

Trin 9: For i = 3 ,

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

Placering af inputArray[3] på den korrekte position i outputArray[]

Trin 10: For i = 2 ,

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

Placering af inputArray[2] på den korrekte position i outputArray[]

Trin 11: For i = 1 ,

Opdatering outputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
Opdater også countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

Placering af inputArray[1] på den korrekte position i outputArray[]

Trin 12: For i = 0,

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

Anbringelse af inputArray[0] på den korrekte position i outputArray[]

Tællesorteringsalgoritme:

  • Erklære et hjælpearray countArray[] af størrelse max(inputArray[])+1 og initialisere den med 0 .
  • Traverse array inputArray[] og kortlæg hvert element af inputArray[] som et indeks over countArray[] array, dvs. eksekvere countArray[inputArray[i]]++ til 0 <= i < N .
  • Beregn præfikssummen ved hvert indeks af array inputArray [].
  • Opret et array outputArray[] af størrelse N .
  • Traverse array inputArray[] fra slut og opdatering outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . Opdater også countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

Nedenfor er implementeringen af ​​ovenstående 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; 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]); // Mapping af hvert element i inputArray[] som et indeks // af countArray[] array for (int i = 0; i countArray[inputArray[i]]++; // Beregning af præfikssum ved hvert indeks // af 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 af input-arrayet const outputArray = countSort(inputArray); // Udskrivning af det sorterede array console.log(outputArray.join(' ')); //Denne kode er bidraget af Utkarsh>

hvad er undtagelseshåndtering i java 

>

>

C++14




#include> using> namespace> std;> vector<>int>>tælSorter(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); // Mapping af hvert element i inputArray[] som et indeks // af countArray[] array for (int i = 0; i countArray[inputArray[i]]++; // Beregning af præfikssum ved hvert indeks // af 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 vektor inputArray = { 4, 3, 12, 1, 5, 5, 3, 9 }; // Output array vektor 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>=>' '>)> 

>

>

Produktion 

1 3 3 4 5 5 9 12>

Kompleksitetsanalyse af tællesort:

  • Tidskompleksitet : O(N+M), hvor N og M er på størrelse med inputArray[] og countArray[] henholdsvis.
    • Worst case: O(N+M).
    • Gennemsnits-case: O(N+M).
    • Bedste tilfælde: O(N+M).
  • Hjælpeplads: O(N+M), hvor N og M er pladsen taget af outputArray[] og countArray[] henholdsvis.

Fordel ved tællesortering:

  • Optællingssortering fungerer generelt hurtigere end alle sammenligningsbaserede sorteringsalgoritmer, såsom flettesortering og quicksort, hvis inputområdet er af størrelsesordenen for antallet af input.
  • At tælle sortering er let at kode
  • Optællingssort er en stabil algoritme .

Ulempe ved tællesort:

  • At tælle sortering virker ikke på decimalværdier.
  • At tælle sortering er ineffektivt, hvis rækken af ​​værdier, der skal sorteres, er meget stor.
  • At tælle sortering er ikke en Sortering på stedet algoritme, den bruger ekstra plads til at sortere array-elementerne.