У овом чланку ћемо разговарати о алгоритму сортирања бројања. Сортирање бројањем је техника сортирања која се заснива на кључевима између одређених опсега. У кодирању или техничким интервјуима за софтверске инжењере, алгоритми за сортирање се често постављају. Дакле, важно је разговарати о теми.
Ова техника сортирања не врши сортирање упоређивањем елемената. Врши сортирање тако што броји објекте који имају различите кључне вредности као што је хеширање. Након тога, он изводи неке аритметичке операције за израчунавање индексне позиције сваког објекта у излазној секвенци. Сортирање бројањем се не користи као алгоритам за сортирање опште намене.
Бројање сортирања је ефикасно када опсег није већи од броја објеката који се сортирају. Може се користити за сортирање негативних улазних вредности.
Сада, да видимо алгоритам сортирања бројања.
Алгоритам
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 се чува на 4тхположај низа бројања. Ако било који елемент није присутан у низу, поставите 0, тј. претпоставимо да елемент '3' није присутан у низу, тако да ће 0 бити ускладиштено на 3рдположај.
Сада, сачувајте кумулативни збир од цоунт елементи низа. То ће помоћи да се елементи поставе на тачан индекс сортираног низа.
филмска глумица Кајал
Слично томе, кумулативни број низа бројача је -
4. Сада пронађите индекс сваког елемента оригиналног низа
Након постављања елемента на његово место, смањите његов број за један. Пре постављања елемента 2, његов број је био 2, али након постављања на његову тачну позицију, нови број за елемент 2 је 1.
Слично томе, након сортирања, елементи низа су -
Сада је низ потпуно сортиран.
Бројање сложености сортирања
Сада, да видимо временску сложеност сортирања бројања у најбољем, просечном и најгорем случају. Видећемо и просторну сложеност сортирања бројања.
1. Временска сложеност
| Случај | време | Сложеност |
|---|---|---|
| Најбољи случај | О(н + к) | |
| Авераге Цасе | О(н + к) | |
| Најгори случај | О(н + к) |
У свим горе наведеним случајевима, временска сложеност сортирања бројања је иста. То је зато што алгоритам пролази н+к пута, без обзира на то како су елементи постављени у низ.
Сортирање бројањем је боље од техника сортирања заснованог на поређењу јер нема поређења између елемената у сортирању бројањем. Али, када су цели бројеви веома велики сортирање бројања је лоше јер се морају креирати низови те величине.
2. Сложеност простора
| Спаце Цомплекити | О(макс.) |
| Стабилно | ДА |
- Просторна сложеност сортирања бројања је О(мак). Што је већи распон елемената, већа је сложеност простора.
Имплементација сортирања бројања
Сада, да видимо програме за сортирање бројања у различитим програмским језицима.
Програм: Напишите програм за имплементацију сортирања бројања у Ц језику.
#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;></=> Излаз
листе у Јави
Дакле, то је све о чланку. Надамо се да ће вам чланак бити користан и информативан.
Овај чланак није био ограничен само на алгоритам. Такође смо разговарали о бројању сложености сортирања, раду и имплементацији у различитим програмским језицима.