Räknar sorteringsalgoritm

I den här handledningen lär du dig hur räkningssortering fungerar. Du hittar också arbetsexempel på räkningssortering i C, C ++, Java och Python.

Räkningssortering är en sorteringsalgoritm som sorterar elementen i en matris genom att räkna antalet förekomster av varje unikt element i matrisen. Räkningen lagras i en hjälpmatris och sorteringen görs genom att kartlägga räkningen som ett index för hjälpmatrisen.

Hur räknar sortering fungerar?

  1. Ta reda på det maximala elementet (låt det vara max) från den givna matrisen. Angiven matris
  2. Initiera en array med längd max+1med alla element 0. Denna array används för att lagra räkningen av elementen i arrayen. Räkna array
  3. Spara räkningen av varje element vid respektive index i countmatrisen
    Till exempel: om räkningen av elementet 3 är 2 lagras 2 i räkneuppsättningens tredje position. Om elementet "5" inte finns i matrisen lagras 0 i 5: e position. Räkna av varje lagrat element
  4. Lagra den kumulativa summan av elementen i räknaren. Det hjälper till att placera elementen i rätt index för den sorterade matrisen. Kumulativt antal
  5. Hitta indexet för varje element i den ursprungliga arrayen i count array. Detta ger det kumulativa antalet. Placera elementet vid indexet beräknat enligt bilden nedan. Räknar sortering
  6. När du har placerat varje element i rätt position minskar du antalet med ett.

Räknar sorteringsalgoritm

 countingSort (array, storlek) max <- hitta största element i array initialisera count array med alla nollor för j <- 0 till storlek hitta det totala antalet för varje unikt element och lagra räkningen vid jth index i count array för i <- 1 för att max hitta den kumulativa summan och lagra den i räknar array själv för j <- storlek ner till 1 återställ elementen till array minska antalet för varje element återställt med 1

Python, Java och C / C ++ exempel

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

Komplexitet

Tidskomplexitet:

Det finns huvudsakligen fyra huvudslingor. (Att hitta det största värdet kan göras utanför funktionen.)

för-loop tid för räkningen
1: a O (max)
2: a O (storlek)
3: e O (max)
4: e O (storlek)

Total komplexitet = O(max)+O(size)+O(max)+O(size)=O(max+size)

  • Värsta fallets komplexitet: O(n+k)
  • Bästa fallkomplexitet: O(n+k)
  • Genomsnittlig fallkomplexitet: O(n+k)

I alla ovanstående fall är komplexiteten densamma, för oavsett hur elementen placeras i matrisen, algoritmen går igenom n+ktider.

Det finns ingen jämförelse mellan några element, så det är bättre än jämförelsebaserade sorteringstekniker. Men det är dåligt om heltalen är mycket stora eftersom matrisen med den storleken bör göras.

Rymdkomplexitet:

Rymdkomplexiteten hos Counting Sort är O(max). Större utbud av element, större är rymdkomplexiteten.

Räknar sorteringsapplikationer

Räkningssortering används när:

  • det finns mindre heltal med flera räkningar.
  • linjär komplexitet är behovet.

Intressanta artiklar...