У цій статті ми обговоримо алгоритм сортування підрахунку. Сортування підрахунком — це метод сортування, який базується на ключах між певними діапазонами. Під час програмування чи технічних співбесід для інженерів програмного забезпечення часто запитують про алгоритми сортування. Тому важливо обговорити тему.
Цей метод сортування не виконує сортування шляхом порівняння елементів. Він виконує сортування шляхом підрахунку об’єктів, які мають різні ключові значення, наприклад хешування. Після цього він виконує деякі арифметичні операції, щоб обчислити позицію індексу кожного об’єкта у вихідній послідовності. Сортування підрахунком не використовується як алгоритм сортування загального призначення.
Сортування за підрахунком ефективне, якщо діапазон не перевищує кількість об’єктів для сортування. Його можна використовувати для сортування від’ємних вхідних значень.
Тепер розглянемо алгоритм сортування підрахунку.
чи може Android грати в gamepigeon
Алгоритм
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. Тепер ми маємо зберегти кількість кожного елемента масиву за відповідним індексом у масиві count.
Лічильник елемента зберігатиметься як - Припустімо, що елемент масиву '4' з'являється двічі, тому кількість елемента 4 дорівнює 2. Отже, 2 зберігається в 4тиспозиція масиву підрахунку. Якщо будь-який елемент відсутній в масиві, помістіть 0, тобто припустимо, що елемент '3' відсутній в масиві, тому 0 буде збережено в 3rdположення.
java значення enum
Тепер збережіть кумулятивну суму рахувати елементи масиву. Це допоможе розмістити елементи за правильним індексом відсортованого масиву.
Подібним чином кумулятивний підрахунок масиву підрахунку є -
stringbuilder
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;></=> Вихід
назва спеціальних символів
Отже, це все про статтю. Сподіваюся, стаття буде для вас корисною та інформативною.
Ця стаття не обмежилася лише алгоритмом. Ми також обговорили підрахунок складності сортування, роботу та реалізацію на різних мовах програмування.