Sorteeralgoritme tellen

In deze tutorial leer je hoe tellen sorteren werkt. Ook vindt u voorbeelden van het tellen van sorteringen in C, C ++, Java en Python.

Counting sort is een sorteeralgoritme dat de elementen van een array sorteert door het aantal keren dat elk uniek element in de array voorkomt te tellen. De telling wordt opgeslagen in een hulparray en het sorteren gebeurt door de telling in kaart te brengen als een index van de hulparray.

Hoe werkt tellen met sorteren?

  1. Zoek het maximale element (laat het zijn max) uit de gegeven array. Gegeven array
  2. Initialiseer een array met lengte max+1met alle elementen 0. Deze array wordt gebruikt voor het opslaan van het aantal elementen in de array. Aantal array
  3. Bewaar de telling van elk element op hun respectievelijke index in countarray.
    Bijvoorbeeld: als de telling van element 3 2 is, dan wordt 2 opgeslagen op de 3e positie van de count array. Als element "5" niet aanwezig is in de array, wordt 0 opgeslagen op de 5e positie. Telling van elk opgeslagen element
  4. Sla de cumulatieve som van de elementen van de count-array op. Het helpt bij het plaatsen van de elementen in de juiste index van de gesorteerde array. Cumulatieve telling
  5. Zoek de index van elk element van de oorspronkelijke array in de count-array. Dit geeft de cumulatieve telling. Plaats het element bij de berekende index zoals weergegeven in onderstaande afbeelding. Sorteren
  6. Nadat u elk element op de juiste positie heeft geplaatst, verlaagt u de telling met één.

Sorteeralgoritme tellen

 countingSort (array, size) max <- vind grootste element in array initialiseer count array met allemaal nullen voor j <- 0 tot grootte vind het totale aantal van elk uniek element en sla het aantal op jde index op in count array voor i <- 1 om max de cumulatieve som te vinden en deze op te slaan in de telarray zelf voor j <- grootte teruggebracht tot 1 de elementen herstellen naar de array, het aantal herstelde elementen met 1 verminderen

Python, Java en C / C ++ voorbeelden

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

Complexiteit

Tijdscomplexiteit:

Er zijn hoofdzakelijk vier hoofdlussen. (Het vinden van de grootste waarde kan buiten de functie worden gedaan.)

for loop tijd van tellen
1e O (max)
2e O (maat)
3e O (max)
4e O (maat)

Algemene complexiteit = O(max)+O(size)+O(max)+O(size)=O(max+size)

  • Complexiteit in het ergste geval: O(n+k)
  • Complexiteit in het beste geval: O(n+k)
  • Gemiddelde casuscomplexiteit: O(n+k)

In alle bovenstaande gevallen is de complexiteit hetzelfde, want ongeacht hoe de elementen in de array worden geplaatst, het algoritme doorloopt n+ktijden.

Er is geen vergelijking tussen elementen, dus het is beter dan op vergelijking gebaseerde sorteertechnieken. Maar het is slecht als de gehele getallen erg groot zijn, omdat de array van die grootte moet worden gemaakt.

Ruimtecomplexiteit:

De ruimtecomplexiteit van Counting Sort is O(max). Hoe groter het aantal elementen, hoe groter de complexiteit van de ruimte.

Sorteerapplicaties tellen

Counting sort wordt gebruikt wanneer:

  • er zijn kleinere gehele getallen met meerdere tellingen.
  • lineaire complexiteit is de behoefte.

Interessante artikelen...