Алгоритм підрахунку сортування

У цьому уроці ви дізнаєтесь, як працює підрахунок сортування. Крім того, ви знайдете робочі приклади підрахунку сортування в C, C ++, Java та Python.

Сортування підрахунку - це алгоритм сортування, який сортує елементи масиву, підраховуючи кількість випадків кожного унікального елемента в масиві. Відлік зберігається у допоміжному масиві, і сортування здійснюється шляхом відображення підрахунку як індексу допоміжного масиву.

Як працює підрахунок сорту?

З’ясуйте максимальний елемент (нехай це буде max) із заданого масиву. Даний масив
Ініціалізуйте масив довжиною max+1з усіма елементами 0. Цей масив використовується для зберігання підрахунку елементів у масиві. Підрахувати масив
Зберігайте підрахунок кожного елемента за відповідним індексом у countмасиві
Наприклад: якщо підрахунок елемента 3 дорівнює 2, тоді 2 зберігається на 3-й позиції масиву відліку. Якщо елемент "5" відсутній у масиві, тоді 0 зберігається в 5-й позиції. Кількість кожного збереженого елемента
Зберігає сукупну суму елементів масиву count. Це допомагає розмістити елементи у правильному індексі відсортованого масиву. Сукупний підрахунок
Знайдіть індекс кожного елемента вихідного масиву в масиві count. Це дає сукупний підрахунок. Помістіть елемент за показником, розрахованим, як показано на малюнку нижче. Лічильний сорт
Поставивши кожен елемент у правильне положення, зменшіть його кількість на одиницю.

Алгоритм підрахунку сортування

 countingSort (масив, розмір) max <- знайти найбільший елемент у масиві ініціалізувати масив count з усіма нулями для j <- 0 до розміру знайти загальний підрахунок кожного унікального елемента та зберегти count у j-му індексі в масиві 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). Чим більший діапазон елементів, тим більша космічна складність.