logo

TechCodeview

Підрахунок сортування – підручники зі структур даних і алгоритмів

Що таке сортування підрахунком?

Підрахунок сортування це без порівняння алгоритм сортування, який добре працює, коли є обмежений діапазон вхідних значень. Це особливо ефективно, коли діапазон вхідних значень невеликий порівняно з кількістю елементів, які потрібно відсортувати. Основна ідея Підрахунок сортування це порахувати частота кожного окремого елемента у вхідному масиві та використовуйте цю інформацію, щоб розмістити елементи в їхніх правильних відсортованих позиціях.

Як працює алгоритм підрахунку сортування?

Крок 1 :



  • Дізнайтеся максимум елемент із заданого масиву.

Пошук максимального елемента в inputArray[]

Крок 2:

  • Ініціалізація a countArray[] довжини макс.+1 з усіма елементами як 0 . Цей масив буде використовуватися для зберігання входжень елементів вхідного масиву.

Ініціалізувати countArray[]



крок 3:

  • В countArray[] , зберігати кількість кожного унікального елемента вхідного масиву за відповідними індексами.
  • Наприклад: Кількість елементів 2 у вхідному масиві є 2. Отже, магазин 2 за індексом 2 в countArray[] . Аналогічно, кількість елементів 5 у вхідному масиві є 1 , отже магазин 1 за індексом 5 в countArray[] .

Підтримувати кількість кожного елемента в countArray[]

крок 4:



  • Зберігайте кумулятивна сума або префікс сума з елементів в countArray[] роблячи countArray[i] = countArray[i – 1] + countArray[i]. Це допоможе розмістити елементи вхідного масиву за правильним індексом у вихідному масиві.

Зберігайте кумулятивну суму в countArray[]

крок 5:

  • Ітерація з кінця вхідного масиву, оскільки обхід вхідного масиву з кінця зберігає порядок рівних елементів, що зрештою робить цей алгоритм сортування стабільний .
  • оновлення outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] .
  • Також оновіть countArray[ inputArray[i] ] = countArray[ inputArray[i] ] – -.

5

Крок 6: Для i = 6 ,

Linux перейменувати каталог

оновлення outputArray[ countArray[ inputArray[6] ] – 1] = inputArray[6]
Також оновіть countArray[ inputArray[6] ] = countArray[ inputArray[6] ]- –

Розміщення inputArray[6] у правильній позиції у outputArray[]

Крок 7: Для i = 5 ,

оновлення outputArray[ countArray[ inputArray[5] ] – 1] = inputArray[5]
Також оновіть countArray[ inputArray[5] ] = countArray[ inputArray[5] ]- –

Розміщення inputArray[5] у правильній позиції у outputArray[]

Крок 8: Для i = 4 ,

оновлення outputArray[ countArray[ inputArray[4] ] – 1] = inputArray[4]
Також оновіть countArray[ inputArray[4] ] = countArray[ inputArray[4] ]- –

Розміщення inputArray[4] у правильній позиції у outputArray[]

Крок 9: Для i = 3 ,

оновлення outputArray[ countArray[ inputArray[3] ] – 1] = inputArray[3]
Також оновіть countArray[ inputArray[3] ] = countArray[ inputArray[3] ]- –

Розміщення inputArray[3] у правильній позиції у outputArray[]

Крок 10: Для i = 2 ,

оновлення outputArray[ countArray[ inputArray[2] ] – 1] = inputArray[2]
Також оновіть countArray[ inputArray[2] ] = countArray[ inputArray[2] ]- –

Розміщення inputArray[2] у правильній позиції у outputArray[]

Крок 11: Для i = 1 ,

оновлення outputArray[ countArray[ inputArray[1] ] – 1] = inputArray[1]
Також оновіть countArray[ inputArray[1] ] = countArray[ inputArray[1] ]- –

Розміщення inputArray[1] у правильній позиції у outputArray[]

Крок 12: Для i = 0,

оновлення outputArray[ countArray[ inputArray[0] ] – 1] = inputArray[0]
Також оновіть countArray[ inputArray[0] ] = countArray[ inputArray[0] ]- –

Розміщення inputArray[0] у правильній позиції у outputArray[]

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

  • Оголосити допоміжний масив countArray[] розміру max(inputArray[])+1 і ініціалізуйте його за допомогою 0 .
  • Траверсний масив inputArray[] і зіставте кожен елемент inputArray[] як індекс countArray[] масив, тобто виконати countArray[inputArray[i]]++ для 0 <= i < N .
  • Обчисліть префіксну суму для кожного індексу масиву inputArray [].
  • Створіть масив вихідний масив[] розміру Н .
  • Траверсний масив inputArray[] від end і update outputArray[ countArray[ inputArray[i] ] – 1] = inputArray[i] . Також оновіть countArray[ inputArray[i] ] = countArray[ inputArray[i] ]- – .

Нижче наведено реалізацію наведеного вище алгоритму:

Java




import> java.util.Arrays;> public> class> CountSort {> >public> static> int>[] countSort(>int>[] inputArray) {> >int> N = inputArray.length;> >int> M =>0>;> >for> (>int> i =>0>; i M = Math.max(M, inputArray[i]); } int[] countArray = new int[M + 1]; for (int i = 0; i countArray[inputArray[i]]++; } for (int i = 1; i <= M; i++) { countArray[i] += countArray[i - 1]; } int[] outputArray = new int[N]; for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[вхідний масив[i]]--; } return outputArray; } public static void main(String[] args) { int[] inputArray = {4, 3, 12, 1, 5, 5, 3, 9}; int[] outputArray = countSort(inputArray); for (int i = 0; i System.out.print(outputArray[i] + ' '); } } }> 

>

>

C#




using> System;> using> System.Collections.Generic;> class> GFG> {> >static> List<>int>>CountSort(Список<>int>>inputArray)> >{> >int> N = inputArray.Count;> >// Finding the maximum element of the array inputArray[].> >int> M = 0;> >for> (>int> i = 0; i M = Math.Max(M, inputArray[i]); // Initializing countArray[] with 0 List countArray = новий список (нове int[M + 1]); // Відображення кожного елемента inputArray[] як індексу // масиву countArray[] для (int i = 0; i countArray[inputArray[i]]++; // Обчислення суми префіксів для кожного індексу // масиву countArray [] для (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from the countArray[] array List outputArray = новий список (нове int[N]); for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[вхідний масив[i]]--; } return outputArray; } // Код драйвера static void Main() { // Вхідний масив Список inputArray = новий список { 4, 3, 12, 1, 5, 5, 3, 9 }; // Вихідний масив List outputArray = CountSort(inputArray); for (int i = 0; i Console.Write(outputArray[i] + ' '); Console.WriteLine(); } }> 

>

>

Javascript




function> countSort(inputArray) {> >const N = inputArray.length;> >// Finding the maximum element of inputArray> >let M = 0;> >for> (let i = 0; i M = Math.max(M, inputArray[i]); } // Initializing countArray with 0 const countArray = new Array(M + 1).fill(0); // Mapping each element of inputArray as an index of countArray for (let i = 0; i countArray[inputArray[i]]++; } // Calculating prefix sum at every index of countArray for (let i = 1; i <= M; i++) { countArray[i] += countArray[i - 1]; } // Creating outputArray from countArray const outputArray = new Array(N); for (let i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[вхідний масив[i]]--; } return outputArray; } // Код драйвера const inputArray = [4, 3, 12, 1, 5, 5, 3, 9]; // Сортування вхідного масиву const outputArray = countSort(inputArray); // Друк відсортованого масиву console.log(outputArray.join(' ')); //Цей код надав Utkarsh>

оновлення java 

>

>

C++14




#include> using> namespace> std;> vector<>int>>countSort(вектор<>int>>& inputArray)> {> >int> N = inputArray.size();> >// Finding the maximum element of array inputArray[].> >int> M = 0;> >for> (>int> i = 0; i M = max(M, inputArray[i]); // Initializing countArray[] with 0 vector countArray(M + 1, 0); // Відображення кожного елемента inputArray[] як індексу // масиву countArray[] для (int i = 0; i countArray[inputArray[i]]++; // Обчислення суми префіксів для кожного індексу // масиву countArray [] для (int i = 1; i<= M; i++) countArray[i] += countArray[i - 1]; // Creating outputArray[] from countArray[] array vector вихідний масив (N); for (int i = N - 1; i>= 0; i--) { outputArray[countArray[inputArray[i]] - 1] = inputArray[i]; countArray[вхідний масив[i]]--; } return outputArray; } // Код драйвера int main() { // Вхідний вектор масиву inputArray = { 4, 3, 12, 1, 5, 5, 3, 9 }; // Вихідний вектор масиву outputArray = countSort(inputArray); for (int i = 0; i cout<< outputArray[i] << ' '; return 0; }> 

>

>

Python3




def> count_sort(input_array):> ># Finding the maximum element of input_array.> >M>=> max>(input_array)> ># Initializing count_array with 0> >count_array>=> [>0>]>*> (M>+> 1>)> ># Mapping each element of input_array as an index of count_array> >for> num>in> input_array:> >count_array[num]>+>=> 1> ># Calculating prefix sum at every index of count_array> >for> i>in> range>(>1>, M>+> 1>):> >count_array[i]>+>=> count_array[i>-> 1>]> ># Creating output_array from count_array> >output_array>=> [>0>]>*> len>(input_array)> >for> i>in> range>(>len>(input_array)>-> 1>,>->1>,>->1>):> >output_array[count_array[input_array[i]]>-> 1>]>=> input_array[i]> >count_array[input_array[i]]>->=> 1> >return> output_array> # Driver code> if> __name__>=>=> '__main__'>:> ># Input array> >input_array>=> [>4>,>3>,>12>,>1>,>5>,>5>,>3>,>9>]> ># Output array> >output_array>=> count_sort(input_array)> >for> num>in> output_array:> >print>(num, end>=>' '>)> 

>

>

Вихід 

1 3 3 4 5 5 9 12>

Аналіз складності підрахунку сортування:

  • Часова складність : O(N+M), де Н і М мають розмір inputArray[] і countArray[] відповідно.
    • Найгірший випадок: O(N+M).
    • Середній випадок: O(N+M).
    • Найкращий випадок: O(N+M).
  • Допоміжний простір: O(N+M), де Н і М займає простір вихідний масив[] і countArray[] відповідно.

Перевага підрахункового сортування:

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

Недоліки підрахункового сортування:

  • Сортування підрахунком не працює з десятковими значеннями.
  • Підрахункове сортування неефективне, якщо діапазон значень, що сортуються, дуже великий.
  • Підрахунок сортування не є Сортування на місці алгоритм, він використовує додатковий простір для сортування елементів масиву.