Tællesorteringsalgoritme

I denne vejledning lærer du, hvordan tællesortering fungerer. Du finder også arbejdseksempler på tællesortering i C, C ++, Java og Python.

Tællesortering er en sorteringsalgoritme, der sorterer elementerne i en matrix ved at tælle antallet af forekomster af hvert unikke element i matrixen. Tællingen er gemt i et hjælpearray, og sorteringen udføres ved at kortlægge tællingen som et indeks over hjælpearrayet.

Hvordan tællesortering fungerer?

  1. Find det maksimale element (lad det være max) fra det givne array. Angivet array
  2. Initialiser en matrix med længde max+1med alle elementer 0. Denne matrix bruges til at lagre antallet af elementerne i arrayet. Tæl array
  3. Gem antallet af hvert element ved deres respektive indeks i countarray
    For eksempel: hvis antallet af element 3 er 2, gemmes 2 i 3. position i count array. Hvis element "5" ikke er til stede i arrayet, gemmes 0 i 5. position. Optælling af hvert lagret element
  4. Gem kumulativ sum af elementerne i tællearrayet. Det hjælper med at placere elementerne i det korrekte indeks i det sorterede array. Kumulativ optælling
  5. Find indekset for hvert element i den oprindelige matrix i count-arrayet. Dette giver det kumulative antal. Placer elementet ved indekset beregnet som vist i figuren nedenfor. Tællesortering
  6. Når du har placeret hvert element på sin korrekte position, skal du reducere antallet med et.

Tællesorteringsalgoritme

 countingSort (array, størrelse) max <- find største element i array initialiser count array med alle nuller for j <- 0 til størrelse find det samlede antal af hvert unikt element og gem tællingen ved jth indeks i count array for i <- 1 for maks. at finde den kumulative sum og gemme den i selve count array for j <- størrelse ned til 1 gendanne elementerne til array reducere antallet af hvert element gendannet med 1

Python, Java og C / C ++ eksempler

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

Kompleksitet

Tidskompleksiteter:

Der er hovedsageligt fire hovedsløjfer. (At finde den største værdi kan gøres uden for funktionen.)

for-loop optællingstid
1. O (maks.)
2. plads O (størrelse)
3. O (maks.)
4. plads O (størrelse)

Samlet kompleksitet = O(max)+O(size)+O(max)+O(size)=O(max+size)

  • Kompleksitet i værste tilfælde: O(n+k)
  • Bedste sagskompleksitet: O(n+k)
  • Gennemsnitlig sagskompleksitet: O(n+k)

I alle ovennævnte tilfælde er kompleksiteten den samme, for uanset hvordan elementerne placeres i arrayet, går algoritmen igennem n+ktider.

Der er ingen sammenligning mellem nogen elementer, så det er bedre end sammenligningsbaserede sorteringsteknikker. Men det er dårligt, hvis heltalene er meget store, fordi arrayet af den størrelse skal laves.

Rumkompleksitet:

Rumkompleksiteten af ​​Counting Sort er O(max). Større række af elementer, større er pladsens kompleksitet.

Optælling af sorteringsapplikationer

Tællesortering bruges, når:

  • der er mindre heltal med flere optællinger.
  • lineær kompleksitet er behovet.

Interessante artikler...