logo

TechCodeview

Skaičiavimo rūšiavimas – duomenų struktūrų ir algoritmų vadovėliai

Kas yra skaičiavimo rūšiavimas?

Skaičiavimas Rūšiuoti yra ne palyginimu pagrįstas rūšiavimo algoritmas, kuris gerai veikia, kai yra ribotas įvesties reikšmių diapazonas. Tai ypač efektyvu, kai įvesties reikšmių diapazonas yra mažas, palyginti su rūšiuojamų elementų skaičiumi. Pagrindinė idėja Skaičiavimas Rūšiuoti yra suskaičiuoti dažnį kiekvieno atskiro elemento įvesties masyve ir naudokite tą informaciją, kad elementai būtų surūšiuoti tinkamose vietose.

Kaip veikia skaičiavimo rūšiavimo algoritmas?

1 žingsnis :



  • Išsiaiškinkite maksimalus elementas iš nurodyto masyvo.

Didžiausio elemento radimas inputArray[]

2 žingsnis:

  • Inicijuoti a countArray[] ilgio maks.+1 su visais elementais kaip 0 . Šis masyvas bus naudojamas įvesties masyvo elementų įvykiams saugoti.

Inicijuoti countArray[]



3 veiksmas:

  • Viduje countArray[] , saugo kiekvieno unikalaus įvesties masyvo elemento skaičių atitinkamuose indeksuose.
  • Pavyzdžiui: Elementų skaičius 2 įvesties masyve yra 2. Taigi, parduotuvė 2 prie indekso 2 viduje countArray[] . Panašiai ir elementų skaičius 5 įvesties masyve yra 1 , vadinasi, parduotuvė 1 prie indekso 5 viduje countArray[] .

Išlaikyti kiekvieno elemento skaičių countArray[]

4 veiksmas:



  • Laikykite kaupiamoji suma arba priešdėlio suma elementų countArray[] darant countArray[i] = countArray[i – 1] + countArray[i]. Tai padės įvesties masyvo elementus įdėti į teisingą indeksą išvesties masyve.

Sukauptą sumą išsaugokite countArray[]

5 veiksmas:

  • Kartoti nuo įvesties masyvo pabaigos ir dėl to, kad perėjus įvesties masyvą nuo galo, išsaugoma lygių elementų tvarka, todėl galiausiai atsiranda šis rūšiavimo algoritmas stabilus .
  • Atnaujinti outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .
  • Taip pat atnaujinti countArray[ inputArray[i] ] = countArray[ inputArray[i] ] – –.

5

6 veiksmas: Jei i = 6 ,

burak ozcivit

Atnaujinti outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
Taip pat atnaujinti countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

InputArray[6] įdėjimas į teisingą poziciją outputArray[]

7 veiksmas: Jei i = 5 ,

Atnaujinti outputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
Taip pat atnaujinti countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

InputArray[5] įdėjimas į teisingą poziciją outputArray[]

8 veiksmas: Jei i = 4 ,

Atnaujinti outputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
Taip pat atnaujinti countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

InputArray[4] įdėjimas į teisingą poziciją outputArray[]

9 veiksmas: Jei i = 3 ,

Atnaujinti outputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
Taip pat atnaujinti countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

InputArray[3] įdėjimas į teisingą poziciją outputArray[]

10 veiksmas: Jei i = 2 ,

Atnaujinti outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
Taip pat atnaujinti countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

InputArray[2] įdėjimas į teisingą poziciją outputArray[]

11 veiksmas: Jei i = 1 ,

Atnaujinti outputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
Taip pat atnaujinti countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

InputArray[1] įdėjimas į teisingą poziciją outputArray[]

12 veiksmas: Jei i = 0,

Atnaujinti outputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
Taip pat atnaujinti countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

InputArray[0] įdėjimas į teisingą poziciją outputArray[]

Skaičiavimo rūšiavimo algoritmas:

  • Paskelbkite pagalbinį masyvą countArray[] dydžio max(inputArray[])+1 ir inicijuokite jį naudodami 0 .
  • Traversinis masyvas inputArray[] ir susieti kiekvieną elementą inputArray[] kaip indeksas countArray[] masyvas, ty vykdyti countArray[inputArray[i]]++ dėl 0 <= i < N .
  • Apskaičiuokite kiekvieno masyvo indekso priešdėlio sumą inputArray [].
  • Sukurkite masyvą outputArray[] dydžio N .
  • Traversinis masyvas inputArray[] nuo pabaigos ir atnaujinti outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . Taip pat atnaujinti countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

Žemiau pateikiamas aukščiau pateikto algoritmo įgyvendinimas:

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]]--; } return 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>>Skaičiuoti Rūšiuoti (sąrašas<>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 = naujas sąrašas (naujas int[M + 1]); // Kiekvieno inputArray[] elemento atvaizdavimas kaip indeksas // countArray[] masyvo for (int i = 0; i countArray[inputArray[i]]++; // Prefikso sumos apskaičiavimas kiekviename masyvo countArray indekse // [] už (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List outputArray = naujas sąrašas (naujas tarpt[N]); for (int i = N - 1; i>= 0; i--) { outputMasyvas[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[inputArray[i]]--; } return outputArray; } // Tvarkyklės kodas static void Main() { // Įvesties masyvo sąrašas inputArray = naujas sąrašas { 4, 3, 12, 1, 5, 5, 3, 9 }; // Išvesties masyvo sąrašas 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]]--; } return outputArray; } // Tvarkyklės kodas const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Įvesties masyvo rūšiavimas const outputArray = countSort(inputArray); // Surūšiuoto masyvo spausdinimas console.log(outputArray.join(' ')); //Šį kodą sukūrė Utkarsh>>

java kaip konvertuoti eilutę į int 

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
  
  #include> using> namespace> std;> vector<>int>>countSort(vektorius<>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);  // Kiekvieno inputArray[] elemento atvaizdavimas kaip indeksas // countArray[] masyvo for (int i = 0; i countArray[inputArray[i]]++; // Prefikso sumos apskaičiavimas kiekviename masyvo countArray indekse // [] už (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--) { outputMasyvas[countArray[inputArray[i]] - 1] = inputArray[i];  countArray[inputArray[i]]--;  } return outputArray; } // Tvarkyklės kodas int main() { // Įvesties masyvo vektorius inputArray = {4, 3, 12, 1, 5, 5, 3, 9};  // Išvesties masyvo vektorius 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>=>' '>)>  
  
 
    
 
>
 
    
 
>
 
  Išvestis  
 
1 3 3 4 5 5 9 12>
 
Skaičiavimo rūšiavimo sudėtingumo analizė:
 
     
  •     Laiko sudėtingumas    : O(N+M), kur    N    ir    M    yra dydžio    inputArray[]    ir    countArray[]    atitinkamai. 
       
    • Blogiausias atvejis: O(N+M).
      •  
    • Vidutinis atvejis: O(N+M).
      •  
    • Geriausias atvejis: O(N+M).
      •  
     
    •  
  •     Pagalbinė erdvė:    O(N+M), kur    N    ir    M    yra užimama erdvė    outputArray[]    ir    countArray[]    atitinkamai.
    •  
 
Skaičiavimo rūšiavimo pranašumas:
 
     
  • Skaičiuojantis rūšiavimas paprastai veikia greičiau nei visi palyginimu pagrįsti rūšiavimo algoritmai, pvz., rūšiavimo sujungimas ir greitasis rūšiavimas, jei įvesties diapazonas atitinka įvesties skaičių.
    •  
  • Skaičiavimo rūšiavimą lengva užkoduoti
    •  
  • Skaičiavimo rūšiavimas yra a    stabilus algoritmas    .
    •  
 
Skaičiavimo rūšiavimo trūkumas:
 
     
  • Skaičiavimo rūšiavimas neveikia naudojant dešimtaines reikšmes.
    •  
  • Skaičiavimo rūšiavimas yra neefektyvus, jei rūšiuojamų reikšmių diapazonas yra labai didelis.
    •  
  • Skaičiavimo rūšiavimas nėra    Rūšiavimas vietoje    algoritmas, jis naudoja papildomos vietos masyvo elementams rūšiuoti.
    •