Counting Sort Algorithm

I denne opplæringen vil du lære hvordan tellingssortering fungerer. Du finner også arbeidseksempler på tellesortering i C, C ++, Java og Python.

Counting sort er en sorteringsalgoritme som sorterer elementene i en matrise ved å telle antall forekomster av hvert unike element i matrisen. Tellingen lagres i en hjelpearrise, og sorteringen gjøres ved å kartlegge tellingen som en indeks for hjelpearrisen.

Hvordan fungerer tellingssortering?

  1. Finn ut det maksimale elementet (la det være max) fra den gitte matrisen. Gitt array
  2. Initialiser en matrise med lengde max+1med alle elementene 0. Denne matrisen brukes til å lagre tellingen av elementene i matrisen. Telle matrise
  3. Lagre tellingen av hvert element ved sin respektive indeks i countmatrisen.
    For eksempel: hvis tellingen av element 3 er 2, blir 2 lagret i den tredje posisjonen til tellingsmatrisen. Hvis elementet "5" ikke er tilstede i matrisen, blir 0 lagret i 5. posisjon. Antall lagrede elementer
  4. Lagre kumulativ sum av elementene i telleoppstillingen. Det hjelper med å plassere elementene i riktig indeks for den sorterte matrisen. Kumulativtall
  5. Finn indeksen til hvert element i den opprinnelige matrisen i tellingsmatrisen. Dette gir den kumulative tellingen. Plasser elementet ved indeksen beregnet som vist i figuren nedenfor. Teller sortering
  6. Når du har plassert hvert element i riktig posisjon, reduserer du antallet med ett.

Counting Sort Algorithm

 countingSort (array, size) max <- finn største element i array initialiser count array med alle nuller for j <- 0 til størrelse finn total antall for hvert unike element og lagre count på jth index i count array for i <- 1 for å maksimalt finne den kumulative summen og lagre den i selve count array for j <- størrelse ned til 1 gjenopprette elementene til array redusere antallet av hvert element gjenopprettet 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:

Det er hovedsakelig fire hovedløkker. (Å finne den største verdien kan gjøres utenfor funksjonen.)

for-loop tid for telling
Første O (maks)
2. plass O (størrelse)
3. O (maks)
4. plass O (størrelse)

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

  • Kompleksitet i verste tilfelle: O(n+k)
  • Beste sakskompleksitet: O(n+k)
  • Gjennomsnittlig sakskompleksitet: O(n+k)

I alle de ovennevnte tilfellene er kompleksiteten den samme fordi uansett hvordan elementene plasseres i matrisen, går algoritmen gjennom n+ktidene.

Det er ingen sammenligning mellom noen elementer, så det er bedre enn sammenligningsbaserte sorteringsteknikker. Men det er ille hvis heltallene er veldig store fordi matrisen av den størrelsen skal lages.

Romkompleksitet:

Plasskompleksiteten til Counting Sort er O(max). Større utvalg av elementer, større er romkompleksiteten.

Teller sorteringsapplikasjoner

Tellingsortering brukes når:

  • det er mindre heltall med flere teller.
  • lineær kompleksitet er behovet.

Interessante artikler...