В тази статия ще обсъдим алгоритъма за сортиране на броене. Сортирането с броене е техника за сортиране, която се основава на ключовете между конкретни диапазони. При програмиране или технически интервюта за софтуерни инженери алгоритмите за сортиране се задават широко. Така че е важно да обсъдим темата.
Тази техника за сортиране не извършва сортиране чрез сравняване на елементи. Той извършва сортиране чрез преброяване на обекти с различни ключови стойности като хеширане. След това той извършва някои аритметични операции, за да изчисли позицията на индекса на всеки обект в изходната последователност. Сортирането чрез броене не се използва като алгоритъм за сортиране с общо предназначение.
Сортирането с преброяване е ефективно, когато обхватът не е по-голям от броя на обектите за сортиране. Може да се използва за сортиране на отрицателните входни стойности.
Сега нека видим алгоритъма за сортиране при броене.
пълна форма ide
Алгоритъм
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
Работа на алгоритъма за сортиране при броене
Сега нека видим работата на алгоритъма за сортиране при броене.
За да разберем работата на алгоритъма за сортиране при броене, нека вземем несортиран масив. Ще бъде по-лесно да разберете сортирането на броенето чрез пример.
Нека елементите на масива са -
1. Намерете максималния елемент от дадения масив. Позволявам макс бъде максималния елемент.
2. Сега инициализирайте масива с дължина максимум + 1 с всичките 0 елемента. Този масив ще се използва за съхраняване на броя на елементите в дадения масив.
3. Сега трябва да съхраним броя на всеки елемент от масива в съответния им индекс в масива за броя.
Броят на елемент ще бъде съхранен като - Да предположим, че елементът от масива '4' се появява два пъти, така че броят на елемент 4 е 2. Следователно, 2 се съхранява на 4thпозиция на масива за преброяване. Ако някой елемент не присъства в масива, поставете 0, т.е. да предположим, че елемент '3' не присъства в масива, така че 0 ще бъде съхранен на 3rdпозиция.
inttostr java
Сега запазете кумулативната сума от броя елементи на масива. Това ще помогне да поставите елементите на правилния индекс на сортирания масив.
По същия начин кумулативният брой на масива за броене е -
конвертиране на низ в число
4. Сега намерете индекса на всеки елемент от оригиналния масив
След като поставите елемент на мястото му, намалете броя му с единица. Преди поставянето на елемент 2, неговият брой беше 2, но след поставянето му на правилната му позиция, новият брой за елемент 2 е 1.
По същия начин, след сортиране, елементите на масива са -
Сега масивът е напълно сортиран.
Преброяване на сложността на сортиране
Сега нека видим времевата сложност на сортирането на броенето в най-добрия случай, средния случай и в най-лошия случай. Ще видим и пространствената сложност на сортирането с броене.
1. Времева сложност
| Случай | време | Сложност |
|---|---|---|
| Най-добър случай | O(n + k) | |
| Среден случай | O(n + k) | |
| Най-лошия случай | O(n + k) |
Във всички горепосочени случаи времевата сложност на сортирането на преброяването е една и съща. Това е така, защото алгоритъмът преминава n+k пъти, независимо от това как са разположени елементите в масива.
Сортирането чрез броене е по-добро от техниките за сортиране, базирани на сравнение, тъй като няма сравнение между елементите при сортирането чрез броене. Но когато целите числа са много големи, сортирането при броене е лошо, защото трябва да се създават масиви с такъв размер.
2. Космическа сложност
| Космическа сложност | O (макс.) |
| Стабилен | ДА |
- Пространствената сложност на сортирането при броене е O(max). Колкото по-голяма е гамата от елементи, толкова по-голяма е пространствената сложност.
Внедряване на сортиране при броене
Сега нека видим програмите за сортиране на броенето на различни езици за програмиране.
програма: Напишете програма за реализиране на сортиране чрез броене на език 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;></=> Изход
възраст на ритик рошан
И така, това е всичко за статията. Надяваме се, че статията ще ви бъде полезна и информативна.
Тази статия не беше ограничена само до алгоритъма. Ние също така обсъдихме отчитането на сложността на сортирането, работата и изпълнението в различни езици за програмиране.