logo

TechCodeview

Counting Lajittelu – Tietorakenteet ja algoritmit opetusohjelmat

Mikä on laskentalajittelu?

Laskennallinen lajittelu on ei-vertailupohjainen lajittelualgoritmi, joka toimii hyvin, kun syötearvoja on rajoitetusti. Se on erityisen tehokasta, kun syötearvojen alue on pieni verrattuna lajiteltujen elementtien määrään. Perusidea takana Laskennallinen lajittelu on laskea taajuus jokaisesta erillisestä elementistä syöttötaulukossa ja sijoittaa elementit oikeisiin lajiteltuihin paikkoihinsa näiden tietojen avulla.

Kuinka laskenta-lajittelualgoritmi toimii?

Vaihe 1 :



  • Ota selvää enimmäismäärä elementti annetusta taulukosta.

Enimmäiselementin etsiminen inputArraysta[]

Vaihe 2:

  • Alusta a countArray[] pituudesta max+1 kaikilla elementeillä kuten 0 . Tätä taulukkoa käytetään syötetaulukon elementtien esiintymien tallentamiseen.

Alusta countArray[]



Vaihe 3:

  • Vuonna countArray[] , tallentaa syöttötaulukon kunkin yksilöllisen elementin määrän vastaaviin indekseihinsä.
  • Esimerkiksi: Elementin määrä 2 syöttötaulukossa on 2. Eli kauppaan 2 indeksissä 2 in countArray[] . Samoin elementtien lukumäärä 5 syöttötaulukossa on 1 , siis kauppa 1 indeksissä 5 in countArray[] .

Säilytä kunkin elementin määrä countArrayssa[]

Vaihe 4:



  • Säilytä kumulatiivinen summa tai etuliitteen summa elementeistä countArray[] tekemällä countArray[i] = countArray[i – 1] + countArray[i]. Tämä auttaa sijoittamaan syöttötaulukon elementit oikeaan hakemistoon tulostetaulukossa.

Tallenna kumulatiivinen summa countArray-tiedostoon[]

Vaihe 5:

  • Iteroi syöttötaulukon lopusta ja koska syötetaulukon läpikulku lopusta säilyttää yhtäläisten elementtien järjestyksen, mikä lopulta tekee tästä lajittelualgoritmista vakaa .
  • Päivittää outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .
  • Myös päivitys countArray[ inputArray[i] ] = countArray[ inputArray[i] ] – –.

5

Vaihe 6: Jos i = 6 ,

knn-algoritmi

Päivittää outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
Myös päivitys countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

InputArray[6] asettaminen oikeaan kohtaan outputArray[]

Vaihe 7: Jos i = 5 ,

Päivittää outputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
Myös päivitys countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

InputArray[5] asettaminen oikeaan kohtaan outputArray[]

Vaihe 8: Jos i = 4 ,

Päivittää outputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
Myös päivitys countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

InputArray[4] asettaminen oikeaan kohtaan outputArray[]

Vaihe 9: Jos i = 3 ,

Päivittää outputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
Myös päivitys countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

InputArray[3] asettaminen oikeaan kohtaan outputArray[]

Vaihe 10: Jos i = 2 ,

Päivittää outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
Myös päivitys countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

InputArray[2] asettaminen oikeaan kohtaan outputArray[]

Vaihe 11: Jos i = 1 ,

Päivittää outputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
Myös päivitys countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

InputArray[1] asettaminen oikeaan kohtaan outputArray[]

Vaihe 12: Jos i = 0,

Päivittää outputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
Myös päivitys countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

Sijoitetaan inputArray[0] oikeaan kohtaan outputArray[]

Laskennan lajittelualgoritmi:

  • Ilmoita aputaulukko countArray[] kooltaan max(inputArray[])+1 ja alusta se 0 .
  • Traverse array inputArray[] ja kartoittaa jokainen elementti inputArray[] indeksinä countArray[] array, eli suorita countArray[syöteMatriisi[i]]++ varten 0 <= i < N .
  • Laske etuliitteen summa jokaisessa taulukon indeksissä inputArray [].
  • Luo taulukko outputArray[] kooltaan N .
  • Traverse array inputArray[] lopusta ja päivitys outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . Myös päivitys countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

Alla on yllä olevan algoritmin toteutus:

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--) { lähtöMatriisi[laskentataulukko[syöteMatriisi[i]] - 1] = syöteMatriisi[i]; countArray[syöteMatriisi[i]]--; } palauttaa 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 = uusi lista (uusi int[M + 1]); // InputArray[]:n jokaisen elementin yhdistäminen countArray[]-taulukon indeksiksi // kohteelle (int i = 0; i countArray[inputArray[i]]++; // Lasketaan etuliitesumman jokaisessa indeksissä // taulukon countArray [] for (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List outputArray = uusi lista (uusi int[N]); for (int i = N - 1; i>= 0; i--) { lähtöMatriisi[laskentataulukko[tuloMatriisi[i]] - 1] = syöteMatriisi[i]; countArray[syöteMatriisi[i]]--; } palauttaa outputArray; } // Ohjainkoodi static void Main() { // Input array List inputArray = uusi lista { 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--) { lähtöMatriisi[laskentataulukko[syöteMatriisi[i]] - 1] = syöteMatriisi[i]; countArray[syöteMatriisi[i]]--; } palauttaa outputArray; } // Ohjainkoodi const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Syöttötaulukon lajittelu const outputArray = countSort(inputArray); // Lajitellun taulukon tulostaminen console.log(outputArray.join(' ')); //Tämän koodin on antanut Utkarsh>>

java rakenne 

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
  
  #include> using> namespace> std;> vector<>int>>countSort(vektori<>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);  // InputArray[]:n jokaisen elementin yhdistäminen countArray[]-taulukon indeksiksi // kohteelle (int i = 0; i countArray[inputArray[i]]++; // Lasketaan etuliitesumman jokaisessa indeksissä // taulukon 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--) { lähtöMatriisi[laskentataulukko[tuloMatriisi[i]] - 1] = syöteMatriisi[i];  countArray[syöteMatriisi[i]]--;  } palauttaa outputArray; } // Ohjainkoodi int main() { // Syöttötaulukkovektori inputArray = { 4, 3, 12, 1, 5, 5, 3, 9 };  // Tulostustaulukkovektori outputArray = countSort(inputArray);  for (int i = 0; i cout<< outputArray[i] << ' ';  return 0; }> 
  
 
    
 
>
 
    
 
>
 
 
Python 3
    
 
     
  
 
    
 
     
     
    
 
 
  
  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>=>' '>)>  
  
 
    
 
>
 
    
 
>
 
  Lähtö  
 
1 3 3 4 5 5 9 12>
 
Laskentalajittelun monimutkaisuusanalyysi:
 
     
  •     Aika monimutkaisuus    : O(N+M), missä    N    ja    M    ovat kokoisia    inputArray[]    ja    countArray[]    vastaavasti. 
       
    • Huonoin tapaus: O(N+M).
      •  
    • Keskimääräinen tapaus: O(N+M).
      •  
    • Paras tapaus: O(N+M).
      •  
     
    •  
  •     Aputila:    O(N+M), missä    N    ja    M    ovat viemä tila    outputArray[]    ja    countArray[]    vastaavasti.
    •  
 
Laskevan lajittelun etu:
 
     
  • Laskennallinen lajittelu toimii yleensä nopeammin kuin kaikki vertailupohjaiset lajittelualgoritmit, kuten yhdistämislajittelu ja pikalajittelu, jos syötealue on syötteiden lukumäärän suuruusluokkaa.
    •  
  • Laskentalajittelu on helppo koodata
    •  
  • Laskentalaji on a    vakaa algoritmi    .
    •  
 
Laskentalajittelun haittapuoli:
 
     
  • Laskentalajittelu ei toimi desimaaliarvoilla.
    •  
  • Lajittelun laskenta on tehotonta, jos lajiteltava arvoalue on erittäin suuri.
    •  
  • Laskentalajittelu ei ole    Lajittelu paikan päällä    Algoritmi, Se käyttää ylimääräistä tilaa taulukon elementtien lajitteluun.
    •