Skaičiavimo rūšiavimo algoritmas

Šioje pamokoje sužinosite, kaip veikia rūšiavimas. Taip pat rasite veikiančių skaičiavimo rūšiavimo pavyzdžių C, C ++, Java ir Python.

Skaičiavimo rūšiavimas yra rūšiavimo algoritmas, rūšiuojantis masyvo elementus, skaičiuojant kiekvieno unikalaus masyvo elemento įvykių skaičių. Skaičius saugomas pagalbiniame masyve ir rūšiavimas atliekamas suskaičiuojant skaičių kaip pagalbinio masyvo indeksą.

Kaip veikia rūšiavimas?

maxIš nurodyto masyvo sužinokite maksimalų elementą (tebūnie ). Pateiktas masyvas
Inicijuokite ilgio masyvą max+1su visais elementais 0. Šis masyvas naudojamas masyvo elementų skaičiui saugoti. Skaičiuokite masyvą
Kiekvieno elemento skaičių laikykite atitinkamame countmasyvo rodyklėje.
Pavyzdžiui: jei 3 elemento skaičius yra 2, 2 yra saugomas 3-ioje skaičiavimo masyvo pozicijoje. Jei elemento „5“ masyve nėra, 0 įrašoma 5 pozicijoje. Kiekvieno saugomo elemento skaičius
Saugokite bendrą matricos elementų sumą. Tai padeda patalpinti elementus į teisingą surūšiuoto masyvo indeksą. Bendras skaičius
Suraskite kiekvieno pradinio masyvo elemento rodyklę skaičiavimo masyve. Tai suteikia bendrą skaičių. Įdėkite elementą į indeksą, apskaičiuotą taip, kaip parodyta žemiau esančiame paveiksle. Skaičiavimo rūšiavimas
Padėję kiekvieną elementą teisingoje padėtyje, sumažinkite jo skaičių vienu.

Skaičiavimo rūšiavimo algoritmas

 countingSort (masyvas, dydis) max <- rasti didžiausią masyvo elementą inicializuoti skaičiaus masyvą su visais nuliais j <- 0 dydžiui surasti bendrą kiekvieno unikalaus elemento skaičių ir išsaugoti skaičių j-ajame indekse skaičiaus masyve i <- 1 maksimaliai surasti kaupiamąją sumą ir laikyti ją pačiame skaičiaus masyve j <- dydis iki 1 atstatyti elementus, kad kiekvieno elemento masyvas sumažėtų 1

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

„Python Java C C ++“

 # Counting sort in Python programming def countingSort(array): size = len(array) output = (0) * size # Initialize count array count = (0) * 10 # Store the count of each elements in count array for i in range(0, size): count(array(i)) += 1 # Store the cummulative count for i in range(1, 10): count(i) += count(i - 1) # Find the index of each element of the original array in count array # place the elements in output array i = size - 1 while i>= 0: output(count(array(i)) - 1) = array(i) count(array(i)) -= 1 i -= 1 # Copy the sorted elements into original array for i in range(0, size): array(i) = output(i) data = (4, 2, 2, 8, 3, 3, 1) countingSort(data) print("Sorted Array in Ascending Order: ") print(data)

 // Counting sort in Java programming import java.util.Arrays; class CountingSort ( void countSort(int array(), int size) ( int() output = new int(size + 1); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) int() count = new int(max + 1); // Initialize count array with all zeros. for (int i = 0; i < max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Driver code public static void main(String args()) ( int() data = ( 4, 2, 2, 8, 3, 3, 1 ); int size = data.length; CountingSort cs = new CountingSort(); cs.countSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Counting sort in C programming #include void countingSort(int array(), int size) ( int output(10); // Find the largest element of the array int max = array(0); for (int i = 1; i max) max = array(i); ) // The size of count must be at least (max+1) but // we cannot declare it as int count(max+1) in C as // it does not support dynamic memory allocation. // So, its size is provided statically. int count(10); // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countingSort(array, n); printArray(array, n); )

 // Counting sort in C++ programming #include using namespace std; void countSort(int array(), int size) ( // The size of count must be at least the (max+1) but // we cannot assign declare it as int count(max+1) in C++ as // it does not support dynamic memory allocation. // So, its size is provided statically. int output(10); int count(10); int max = array(0); // Find the largest element of the array for (int i = 1; i max) max = array(i); ) // Initialize count array with all zeros. for (int i = 0; i <= max; ++i) ( count(i) = 0; ) // Store the count of each element for (int i = 0; i < size; i++) ( count(array(i))++; ) // Store the cummulative count of each array for (int i = 1; i <= max; i++) ( count(i) += count(i - 1); ) // Find the index of each element of the original array in count array, and // place the elements in output array for (int i = size - 1; i>= 0; i--) ( output(count(array(i)) - 1) = array(i); count(array(i))--; ) // Copy the sorted elements into original array for (int i = 0; i < size; i++) ( array(i) = output(i); ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int array() = (4, 2, 2, 8, 3, 3, 1); int n = sizeof(array) / sizeof(array(0)); countSort(array, n); printArray(array, n); )

Sudėtingumas

Laiko sudėtingumas:

Daugiausia yra keturios pagrindinės kilpos. (Rasti didžiausią vertę galima ne funkcijoje.)

for-loop	skaičiavimo laikas
1-oji	O (maks.)
2-oji	O (dydis)
3 d	O (maks.)
4-oji	O (dydis)

Bendras sudėtingumas = O(max)+O(size)+O(max)+O(size)=O(max+size)

Blogiausio atvejo sudėtingumas: O(n+k)
Geriausio atvejo sudėtingumas: O(n+k)
Vidutinis atvejų sudėtingumas: O(n+k)

Visais aukščiau išvardytais atvejais sudėtingumas yra tas pats, nes nesvarbu, kaip elementai dedami į masyvą, algoritmas eina per n+klaiką.

Nėra jokio elemento palyginimo, todėl jis yra geresnis nei palyginimu pagrįstos rūšiavimo technikos. Tačiau blogai, jei sveiki skaičiai yra labai dideli, nes turėtų būti padarytas tokio dydžio masyvas.

Erdvės sudėtingumas:

Skaičiavimo rūšiavimo erdvės sudėtingumas yra O(max). Didesnis elementų asortimentas, didesnis erdvės sudėtingumas.