Алгоритам бројања сортирања

У овом упутству ћете научити како функционише бројање сортирања. Такође, наћи ћете и радне примере бројања сортирања у Ц, Ц ++, Јава и Питхон.

Бројање сортирања је алгоритам сортирања који сортира елементе низа бројећи број појављивања сваког јединственог елемента у низу. Бројање се чува у помоћном низу и сортирање се врши мапирањем броја као индекса помоћног низа.

Како бројање сортирања функционише?

  1. Дознајте максимални елемент (нека буде max) из датог низа. Дат низ
  2. Иницијализујте низ дужине max+1са свим елементима 0. Овај низ се користи за складиштење броја елемената у низу. Броји низ
  3. Похраните бројање сваког елемента у његов одговарајући индекс у countпоље
    На пример: ако је број елемента 3 2, онда се 2 чува на 3. месту низа бројања. Ако елемент „5“ није присутан у низу, тада се 0 чува на 5. месту. Бројање сваког сачуваног елемента
  4. Похранити кумулативни збир елемената низа бројања. Помаже у постављању елемената у тачан индекс разврстаног низа. Кумулативни број
  5. Пронађите индекс сваког елемента изворног низа у низу бројања. Ово даје кумулативни број. Поставите елемент на индекс израчунат како је приказано на доњој слици. Бројање сорте
  6. Након постављања сваког елемента у његов тачан положај, смањите његов број за један.

Алгоритам бројања сортирања

 цоунтингСорт (низ, величина) мак <- пронађи највећи елемент у низу иницијализуј низ низа са свим нулама за ј <- 0 до величине пронађи укупан број сваког јединственог елемента и сачувај бројање у ј-том индексу у низу броја за и <- 1 максимално пронаћи кумулативни зброј и сачувати га у самом низу цоунт за ј <- величина до 1 вратити елементе у низ смањити број сваког елемента враћеног за 1

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц ++ 
 # 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); )

Сложеност

Сложеност времена:

Углавном постоје четири главне петље. (Проналажење највеће вредности може се обавити изван функције.)

фор-лооп време бројања
1ст О (макс.)
2нд О (величина)
3. О (макс.)
4тх О (величина)

Укупна сложеност = O(max)+O(size)+O(max)+O(size)=O(max+size)

  • Најгора сложеност случаја: O(n+k)
  • Најбољи случај сложености: O(n+k)
  • Просечна сложеност предмета: O(n+k)

У свим горе наведеним случајевима сложеност је иста јер, без обзира на то како су елементи постављени у низу, алгоритам пролази кроз n+kвремена.

Не постоји поређење ни са једним елементом, па је боље од техника сортирања заснованих на поређењу. Али, лоше је ако су цели бројеви веома велики, јер треба направити низ те величине.

Сложеност простора:

Сложеност простора Бројања сорте је O(max). Што је већи распон елемената, већа је и сложеност простора.

Бројање сортираних апликација

Сортирање бројањем се користи када:

  • постоје мањи цели бројеви са вишеструким бројањем.
  • линеарна сложеност је потреба.

Занимљиви Чланци...