W tym artykule omówimy algorytm sortowania zliczającego. Sortowanie przez zliczanie to technika sortowania oparta na kluczach pomiędzy określonymi zakresami. Podczas rozmów kwalifikacyjnych związanych z kodowaniem lub technicznymi programistami często zadaje się pytanie o algorytmy sortowania. Dlatego ważne jest, aby omówić ten temat.
Ta technika sortowania nie polega na sortowaniu poprzez porównywanie elementów. Wykonuje sortowanie poprzez zliczanie obiektów mających różne wartości kluczowe, takie jak hashowanie. Następnie wykonuje pewne operacje arytmetyczne, aby obliczyć pozycję indeksu każdego obiektu w sekwencji wyjściowej. Sortowanie przez zliczanie nie jest używane jako algorytm sortowania ogólnego przeznaczenia.
Sortowanie zliczające jest skuteczne, gdy zakres nie jest większy niż liczba sortowanych obiektów. Można go używać do sortowania ujemnych wartości wejściowych.
Przyjrzyjmy się teraz algorytmowi sortowania przez zliczanie.
mójlivecricket w
Algorytm
countingSort(array, n) // 'n' is the size of array max = find maximum element in the given array create count array with size maximum + 1 Initialize count array with all 0's for i = 0 to n find the count of every unique element and store that count at ith position in the count array for j = 1 to max Now, find the cumulative sum and store it in count array for i = n to 1 Restore the array elements Decrease the count of every restored element by 1 end countingSort
Działanie algorytmu sortowania zliczającego
Przyjrzyjmy się teraz działaniu algorytmu sortowania zliczającego.
Aby zrozumieć działanie algorytmu sortowania przez zliczanie, weźmy nieposortowaną tablicę. Sortowanie przez zliczanie będzie łatwiejsze do zrozumienia na przykładzie.
Niech elementami tablicy są -
1. Znajdź element maksymalny z podanej tablicy. Pozwalać maks być elementem maksymalnym.
2. Teraz zainicjuj tablicę długości maks. + 1 mający wszystkie 0 elementów. Tablica ta będzie używana do przechowywania liczby elementów w danej tablicy.
3. Teraz musimy zapisać liczbę każdego elementu tablicy pod odpowiednim indeksem w tablicy count.
Liczba elementów zostanie zapisana jako - Załóżmy, że element tablicy „4” pojawi się dwa razy, więc liczba elementu 4 wyniesie 2. Zatem 2 jest przechowywane w pozycji 4tpozycja tablicy liczników. Jeśli w tablicy nie ma żadnego elementu, umieść 0, tzn. załóżmy, że w tablicy nie ma elementu „3”, więc 0 zostanie zapisane w pozycji 3r & Dpozycja.
Teraz zapisz skumulowaną sumę liczyć elementy tablicy. Pomoże to w umieszczeniu elementów we właściwym indeksie posortowanej tablicy.
Podobnie skumulowana liczba tablicy count wynosi -
4. Teraz znajdź indeks każdego elementu oryginalnej tablicy
Po umieszczeniu elementu na swoim miejscu zmniejsz jego liczbę o jeden. Przed umieszczeniem elementu 2 jego liczba wynosiła 2, ale po umieszczeniu go we właściwym miejscu nowa liczba elementu 2 wynosi 1.
system.out.println
Podobnie po posortowaniu elementy tablicy są -
Teraz tablica jest całkowicie posortowana.
Liczenie złożoności sortowania
Przyjrzyjmy się teraz złożoności czasowej sortowania przez zliczanie w najlepszym przypadku, średnim i najgorszym przypadku. Zobaczymy także złożoność przestrzenną sortowania zliczającego.
1. Złożoność czasowa
| Sprawa | Czas | Złożoność |
|---|---|---|
| Najlepszy przypadek | O(n + k) | |
| Przeciętny przypadek | O(n + k) | |
| Najgorszy przypadek | O(n + k) |
We wszystkich powyższych przypadkach złożoność czasowa sortowania zliczającego jest taka sama. Dzieje się tak, ponieważ algorytm przechodzi n+k razy, niezależnie od sposobu umieszczenia elementów w tablicy.
Podstawowe informacje o kompilacji Ubuntu
Sortowanie przez zliczanie jest lepsze niż techniki sortowania opartego na porównaniach, ponieważ podczas sortowania przez zliczanie nie ma porównania między elementami. Ale gdy liczby całkowite są bardzo duże, sortowanie przez zliczanie jest złe, ponieważ trzeba utworzyć tablice o tym rozmiarze.
2. Złożoność przestrzeni
| Złożoność przestrzeni | O(maks.) |
| Stabilny | TAK |
- Złożoność przestrzenna sortowania zliczającego wynosi O(max). Im większy zakres elementów, tym większa złożoność przestrzeni.
Implementacja sortowania zliczającego
Przyjrzyjmy się teraz programom sortowania liczącego w różnych językach programowania.
Program: Napisz program realizujący sortowanie przez zliczanie w języku C.
#include int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 16 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; printf('%d ', a[i]); main() a[]="{" 11, 30, 24, 7, 31, }; n="sizeof(a)/sizeof(a[0]);" printf('before sorting are -
'); printarr(a, n); countsort(a, printf('
after return 0; pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-12.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 11 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; cout< <a[i]<<' '; main() a[]="{" 31, 11, 42, 7, 30, }; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting are -
'; printarr(a, n); countsort(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-13.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C#.</p> <pre> using System; class CountingSort { static int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } static void countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 3 i++) { a[i]="output[i];" store the sorted elements into main array } static void printarr(int[] a, int n) * function to print i; for (i="0;" i < n; console.write(a[i] + ' '); main() int[] a="{" 43, 31, 2, 7, 10, 1, 5, 6, }; n="a.Length;" console.write('before sorting are -
'); printarr(a,n); countsort(a,n); console.write('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-14.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in Java.</p> <pre> class CountingSort { int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); //int max = 42; int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 41 i++) { a[i]="output[i];" store the sorted elements into main array } * function to print void printarray(int a[], int n) i; for (i="0;" i < n; system.out.print(a[i] + ' '); public static main(string args[]) a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="a.length;" countingsort c1="new" countingsort(); system.out.println('
before sorting are - c1.printarray(a, n); c1.countsort(a,n); system.out.println('
after system.out.println(); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-15.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in PHP.</p> <pre> <?php function getMax($a, $n) { $max = $a[0]; for($i = 1; $i $max) $max = $a[$i]; } return $max; //maximum element from the array } function countSort(&$a, $n) // function to perform counting sort { $LeftArray = array($n + 1); $max = getMax($a, $n); $count = array($max + 1); //create count array with size [max+1] for ($i = 0; $i <= $max; ++$i) { $count[$i] = 0; // Initialize count array with all zeros } for ($i = 0; $i < $n; $i++) // Store the count of each element { $count[$a[$i]]++; } for($i = 1; $i= 0; $i--) { $output[$count[$a[$i]] - 1] = $a[$i]; $count[$a[$i]]--; // decrease count for same numbers } for($i = 0; $i<$n; $i++) { $a[$i] = $output[$i]; //store the sorted elements into main array } } /* Function to print the array elements */ function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 9, 28, 22, 5, 29, 14, 37, 28, 9 ); $n = count($a); echo 'Before sorting array elements are - <br>'; printArray($a, $n); countSort($a,$n); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-16.webp" alt="Counting Sort"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed counting sort complexity, working, and implementation in different programming languages.</p> <hr></n;></=></pre></n;></=></pre></n;></=></pre></n;></=> Wyjście
To tyle na temat artykułu. Mam nadzieję, że artykuł będzie dla Ciebie pomocny i pouczający.
Artykuł ten nie ograniczał się tylko do algorytmu. Omówiliśmy także złożoność sortowania przez zliczanie, działanie i implementację w różnych językach programowania.