В този урок ще научите как работи преброяването на сортирането. Също така ще намерите работещи примери за преброяване на сортиране в C, C ++, Java и Python.
Сортирането за броене е алгоритъм за сортиране, който сортира елементите на масив, като брои броя на появите на всеки уникален елемент в масива. Броят се съхранява в спомагателен масив и сортирането се извършва чрез картографиране на броя като индекс на помощния масив.
Как работи преброяването на сортирането?
- Открийте максималния елемент (нека бъде
max) от дадения масив.
Даден масив - Инициализирайте масив с дължина
max+1с всички елементи 0. Този масив се използва за съхраняване на броя на елементите в масива.
Брой масив - Съхранявайте броя на всеки елемент в съответния им индекс в
countмасив
Например: ако броят на елемент 3 е 2, тогава 2 се съхранява в третата позиция на масива за броене. Ако елементът "5" не присъства в масива, тогава 0 се съхранява на 5-то място.
Брой на всеки съхранен елемент - Съхранява кумулативна сума от елементите на масива за броене. Помага при поставянето на елементите в правилния индекс на сортирания масив.
Кумулативен брой - Намерете индекса на всеки елемент от оригиналния масив в масива за броене. Това дава кумулативния брой. Поставете елемента в индекса, изчислен, както е показано на фигурата по-долу.
Преброяване сортиране - След като поставите всеки елемент в правилната му позиция, намалете броя му с един.
Алгоритъм за преброяване на сортиране
countingSort (масив, размер) max <- намиране на най-големия елемент в масива инициализиране на масив count с всички нули за j <- 0 за размер намиране на общия брой на всеки уникален елемент и съхраняване на броя в jth индекс в масив count за i <- 1 за максимално намиране на кумулативната сума и съхраняването й в самия масив count за j <- размер до 1 възстановяване на елементите в масив намаляване брой на всеки елемент, възстановен с 1
Примери за Python, Java и C / C ++
Python Java C C ++ # 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); )
Сложност
Сложни времена:
Основно има четири основни бримки. (Намирането на най-голямата стойност може да се направи извън функцията.)
| for-loop | време на броене |
|---|---|
| 1-ви | O (макс.) |
| 2-ри | O (размер) |
| 3-ти | O (макс.) |
| 4-ти | O (размер) |
Обща сложност O(max)+O(size)+O(max)+O(size)=O(max+size)
- Най-лошата сложност:
O(n+k) - Най-добрата сложност:
O(n+k) - Средна сложност на случая:
O(n+k)
Във всички горепосочени случаи сложността е една и съща, защото без значение как са поставени елементите в масива, алгоритъмът преминава през n+kпъти.
Няма сравнение между никакви елементи, така че е по-добре от базирани на сравнение техники за сортиране. Но е лошо, ако целите числа са много големи, защото трябва да се направи масивът с този размер.
Космическа сложност:
Сложността на пространството при сортиране на преброяване е O(max). Колкото по-голям е диапазонът от елементи, толкова по-голяма е сложността на пространството.
Преброяване на приложения за сортиране
Сортирането при броене се използва, когато:
- има по-малки цели числа с множество отброявания.
- линейната сложност е необходимостта.
