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.
2 žingsnis:
- Inicijuoti a countArray[] ilgio maks.+1 su visais elementais kaip 0 . Šis masyvas bus naudojamas įvesties masyvo elementų įvykiams saugoti.
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[] .
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.
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] ] – –.
6 veiksmas: Jei i = 6 ,
burak ozcivit
Atnaujinti outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
Taip pat atnaujinti countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –
7 veiksmas: Jei i = 5 ,
Atnaujinti outputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
Taip pat atnaujinti countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –
8 veiksmas: Jei i = 4 ,
Atnaujinti outputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
Taip pat atnaujinti countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –
9 veiksmas: Jei i = 3 ,
Atnaujinti outputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
Taip pat atnaujinti countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –
10 veiksmas: Jei i = 2 ,
Atnaujinti outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
Taip pat atnaujinti countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –
11 veiksmas: Jei i = 1 ,
Atnaujinti outputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
Taip pat atnaujinti countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –
12 veiksmas: Jei i = 0,
Atnaujinti outputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
Taip pat atnaujinti countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –
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 |
>
>
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švestis1 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.