logo

TechCodeview

Räknesortering – Självstudier för datastrukturer och algoritmer

Vad är räknesortering?

Räknesortering är en icke-jämförelsebaserad sorteringsalgoritm som fungerar bra när det finns begränsat antal indatavärden. Det är särskilt effektivt när intervallet av ingångsvärden är litet jämfört med antalet element som ska sorteras. Grundtanken bakom Räknesortering är att räkna frekvens av varje distinkt element i inmatningsmatrisen och använd den informationen för att placera elementen i deras korrekt sorterade positioner.

Hur fungerar Counting Sort Algorithm?

Steg 1 :



  • Ta reda på maximal element från den givna arrayen.

Hitta maximalt element i inputArray[]

Steg 2:

  • Initiera a countArray[] av längd max+1 med alla element som 0 . Denna matris kommer att användas för att lagra förekomsterna av elementen i inmatningsmatrisen.

Initiera countArray[]



Steg 3:

  • I den countArray[] lagrar antalet för varje unikt element i inmatningsmatrisen vid deras respektive index.
  • Till exempel: Antalet element 2 i inmatningsmatrisen är 2. Så, butik 2 vid index 2 i countArray[] . På samma sätt, antalet element 5 i inmatningsmatrisen är 1 , därav butik 1 vid index 5 i countArray[] .

Upprätthåll antalet av varje element i countArray[]

Steg 4:



  • Förvara kumulativ summa eller prefix summa av elementen i countArray[] genom att göra countArray[i] = countArray[i – 1] + countArray[i]. Detta kommer att hjälpa till att placera elementen i inmatningsmatrisen vid rätt index i utmatrisen.

Lagra den ackumulerade summan i countArray[]

Steg 5:

  • Iterera från änden av inmatningsmatrisen och eftersom korsning av inmatningsmatrisen från änden bevarar ordningen av lika element, vilket så småningom gör denna sorteringsalgoritm stabil .
  • Uppdatering outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .
  • Uppdatera också countArray[ inputArray[i] ] = countArray[ inputArray[i] ] – -.

5

Steg 6: För i = 6 ,

skal sortera

Uppdatering outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
Uppdatera också countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

Placera inputArray[6] på rätt plats i outputArray[]

Steg 7: För i = 5 ,

Uppdatering outputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
Uppdatera också countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

Placera inputArray[5] på rätt plats i outputArray[]

Steg 8: För i = 4 ,

Uppdatering outputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
Uppdatera också countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

Placera inputArray[4] på rätt plats i outputArray[]

Steg 9: För i = 3 ,

Uppdatering outputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
Uppdatera också countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

Placera inputArray[3] på rätt plats i outputArray[]

Steg 10: För i = 2 ,

Uppdatering outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
Uppdatera också countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

Placera inputArray[2] på rätt plats i outputArray[]

Steg 11: För i = 1 ,

Uppdatering outputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
Uppdatera också countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

Placera inputArray[1] på rätt plats i outputArray[]

Steg 12: För i = 0,

Uppdatering outputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
Uppdatera också countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

Placera inputArray[0] på rätt plats i outputArray[]

Räknesorteringsalgoritm:

  • Deklarera en extra array countArray[] av storlek max(inputArray[])+1 och initiera den med 0 .
  • Traverse array inputArray[] och kartlägga varje element av inputArray[] som ett index på countArray[] array, dvs exekvera countArray[inputArray[i]]++ för 0 <= i < N .
  • Beräkna prefixsumman vid varje index av array inputArray [].
  • Skapa en array outputArray[] av storlek N .
  • Traverse array inputArray[] från slutet och uppdatera outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . Uppdatera också countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

Nedan är implementeringen av ovanstående algoritm:

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]]--; } returnera 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(List<>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 lista (ny int[M + 1]); // Mappning av varje element i inputArray[] som ett index // av countArray[] array för (int i = 0; i countArray[inputArray[i]]++; // Beräknar prefixsumma vid varje index // av array countArray [] för (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List outputArray = ny lista (ny int[N]); för (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } returnera outputArray; } // Driver code static void Main() { // Input array List inputArray = ny lista { 4, 3, 12, 1, 5, 5, 3, 9}; // Output array List outputArray = CountSort(inputArray); för (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]]--; } returnera outputArray; } // Drivrutinskod const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Sortering av inmatningsmatrisen const outputArray = countSort(inputArray); // Skriver ut den sorterade arrayen console.log(outputArray.join(' ')); //Denna kod bidrar med Utkarsh>

cdr full form 

>

>

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); // Mappning av varje element i inputArray[] som ett index // av countArray[] array för (int i = 0; i countArray[inputArray[i]]++; // Beräknar prefixsumma vid varje index // av array countArray [] för (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from countArray[] array vector outputArray(N); för (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } returnera outputArray; } // Drivrutinskod int main() { // Indatamatrisvektor inputArray = { 4, 3, 12, 1, 5, 5, 3, 9 }; // Utmatningsvektor outputArray = countSort(inputArray); för (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>

Komplexitetsanalys av räkneslag:

  • Tidskomplexitet : O(N+M), där N och M är storleken på inputArray[] och countArray[] respektive.
    • Värsta fall: O(N+M).
    • Medel-case: O(N+M).
    • Bästa fall: O(N+M).
  • Hjälputrymme: O(N+M), där N och M är utrymmet som tas av outputArray[] och countArray[] respektive.

Fördel med räknesortering:

  • Räknesortering fungerar generellt snabbare än alla jämförelsebaserade sorteringsalgoritmer, såsom sammanslagningssortering och snabbsortering, om indataområdet är i storleksordningen av antalet indata.
  • Räkna sortering är lätt att koda
  • Räkna sort är en stabil algoritm .

Nackdelen med räknesortering:

  • Att räkna sortering fungerar inte på decimalvärden.
  • Att räkna sortering är ineffektivt om intervallet av värden som ska sorteras är mycket stort.
  • Att räkna sort är inte en Sortering på plats algoritm, Den använder extra utrymme för att sortera arrayelementen.