Подсчет алгоритма сортировки

В этом уроке вы узнаете, как работает подсчетная сортировка. Также вы найдете рабочие примеры сортировки с подсчетом в 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 (array, size) max <- найти самый большой элемент в массиве инициализировать массив счетчиков со всеми нулями для j <- 0 для размера найти общее количество каждого уникального элемента и сохранить счет в j-м индексе в массиве count для i <- 1 to max найти кумулятивную сумму и сохранить ее в самом массиве count для j <- size до 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-й О (размер)
3-й O (макс.)
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). Чем больше набор элементов, тем больше сложность пространства.

Подсчет приложений сортировки

Счетная сортировка используется, когда:

  • есть меньшие целые числа с несколькими счетчиками.
  • линейная сложность - это необходимость.

Интересные статьи...