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

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

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

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

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

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

 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). Чим більший діапазон елементів, тим більша космічна складність.

Підрахунок заявок на сортування

Сортування підрахунку використовується, коли:

  • є менші цілі числа з кількома відліками.
  • лінійна складність - це потреба.

Цікаві статті...