Algoritmus počítání řazení

V tomto kurzu se dozvíte, jak počítání řazení funguje. Také najdete pracovní příklady počítání řazení v C, C ++, Java a Python.

Počítání řazení je třídicí algoritmus, který třídí prvky pole počítáním počtu výskytů každého jedinečného prvku v poli. Počet je uložen v pomocném poli a třídění se provádí mapováním počtu jako indexu pomocného pole.

Jak počítání řazení funguje?

  1. Zjistěte maximální prvek (nechť je max) z daného pole. Dané pole
  2. Inicializujte pole délky max+1se všemi prvky 0. Toto pole se používá pro ukládání počtu prvků v poli. Počítat pole
  3. Uložte počet každého prvku na jejich příslušný index v countpoli
    Například: pokud je počet prvku 3 2, pak je 2 uložen na 3. pozici pole počtu. Pokud prvek "5" není v poli, pak je 0 uložen na 5. pozici. Počet každého uloženého prvku
  4. Uložte kumulativní součet prvků počítacího pole. Pomáhá při umisťování prvků do správného indexu seřazeného pole. Kumulativní počet
  5. Najděte index každého prvku původního pole v poli počítání. To dává kumulativní počet. Umístěte prvek na index vypočítaný podle obrázku níže. Počítání řazení
  6. Po umístění každého prvku do správné polohy snižte jeho počet o jeden.

Algoritmus počítání řazení

 counttingSort (pole, velikost) max <- najít největší prvek v poli inicializovat count pole se všemi nulami pro j <- 0 na velikost najít celkový počet každého jedinečného prvku a uložit počet na jth indexu v count poli pro i <- 1 maximálně najít kumulativní součet a uložit jej do samotného počtu count pro j <- velikost do 1 obnovit prvky do pole snížit počet každého prvku obnoveného o 1

Python, Java a C / C ++ příklady

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); )

Složitost

Časová složitost:

Existují hlavně čtyři hlavní smyčky. (Nalezení největší hodnoty lze provést mimo funkci.)

pro smyčku čas počítání
1. místo O (max.)
2. místo O (velikost)
3. místo O (max.)
4. místo O (velikost)

Složitost celého = O(max)+O(size)+O(max)+O(size)=O(max+size)

  • Složitost nejhoršího případu: O(n+k)
  • Nejlepší složitost případu: O(n+k)
  • Průměrná složitost případu: O(n+k)

Ve všech výše uvedených případech je složitost stejná, protože bez ohledu na to, jak jsou prvky umístěny v poli, algoritmus prochází n+kčasy.

Neexistuje žádné srovnání mezi žádnými prvky, takže je lepší než techniky třídění založené na srovnání. Je však špatné, pokud jsou celá čísla velmi velká, protože by se mělo vytvořit pole této velikosti.

Složitost prostoru:

Složitost prostoru počítání řazení je O(max). Čím větší je rozsah prvků, tím větší je prostorová složitost.

Počítání aplikací řazení

Počítání se používá, když:

  • existují menší celá čísla s více počty.
  • lineární složitost je potřeba.

Zajímavé články...