Сортировка подсчётом кратко

Привет, Вы узнаете о том , что такое сортировка подсчётом, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое сортировка подсчётом, сортировка подсчетом , настоятельно рекомендую прочитать все из категории Качество и тестирование программного обеспечения. Quality Assurance..

сортировка подсчетом (англ. counting sort ; сортировка посредством подсчета англ. sorting by counting ) — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчета совпадающих элементов. Применение сортировки подсчетом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000.

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

Простой алгоритм

Это простейший вариант алгоритма. Создать вспомогательный массив C[0..k - 1], состоящий из нулей, затем последовательно прочитать элементы входного массива A, для каждого A[i] увеличить C[A[i]] на единицу. Теперь достаточно пройти по массиву C, для каждого {\displaystyle j\in \{0,...,k-1\}} в массив A последовательно записать число j C[j] раз.

SimpleCountingSort:
    for i = 0 to k - 1
        C[i] = 0;
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;
    b = 0;
    for j = 0 to k - 1
        for i = 0 to C[j] - 1
            A[b] = j;
            b = b + 1;

Это же решение на c++.

void countingSort(int* array, int n, int k) {
	int c[k+1] = { 0 };
	for (int i = 0; i < n; i++) {
		c[array[i]] = c[array[i]] + 1;
	}
		
	int b = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < c[i]; j++) {
			array[b] = i;
			b = b + 1;
		}
	}	
}

Алгоритм со списком

Этот вариант (англ. pigeonhole sorting, count sort) используется, когда на вход подается массив структур данных, который следует отсортировать по ключам (key). Нужно создать вспомогательный массив C[0..k - 1], каждый C[i] в дальнейшем будет содержать список элементов из входного массива. Затем последовательно прочитать элементы входного массива A, каждый A[i] добавить в список C[A[i].key]. В заключении пройти по массиву C, для каждого {\displaystyle j\in \{0,...,k-1\}} в массив A последовательно записывать элементы списка C[j]. Алгоритм устойчив.

ListCountingSort
    for i = 0 to k - 1
        C[i] = NULL;
    for i = 0 to n - 1
        C[A[i].key].add(A[i]);
    b = 0;
    for j = 0 to k - 1
        p = C[j];
        while p != NULL
            A[b] = p.data;
            p = p.next();
            b = b + 1;

Устойчивый алгоритм

В этом варианте помимо входного массива A потребуется два вспомогательных массива — C[0..k - 1] для счетчика и B[0..n - 1] для отсортированного массива. Сначала следует заполнить массив C нулями, и для каждого A[i] увеличить C[A[i]] на 1. Далее подсчитывается количество элементов меньших или равных. Для этого каждый C[j], начиная с C , увеличивают на C[j - 1]. Таким образом в последней ячейке будет находиться количество элементов от до существующих во входном массиве. На последнем шаге алгоритма читается входной массив с конца, значение C[A[i]] уменьшается на 1 и в каждый B[C[A[i]]] записывается A[i]. Алгоритм устойчив.

StableCountingSort
    for i = 0 to k - 1
        C[i] = 0;
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;
    for j = 1 to k - 1
        C[j] = C[j] + C[j - 1];
    for i = n - 1 to 0
        C[A[i]] = C[A[i]] - 1;
        B[C[A[i]]] = A[i];

Обобщение на произвольный целочисленный диапазон

Возникает несколько вопросов. Что делать, если диапазон значений (min и max) заранее не известен? Что делать, если минимальное значение больше нуля или в сортируемых данных присутствуют отрицательные числа? Первый вопрос можно решить линейным поиском min и max, что не повлияет на асимптотику алгоритма. Второй вопрос несколько сложнее. Если min больше нуля, то следует при работе с массивом C из A[i] вычитать min, а при обратной записи прибавлять. При наличии отрицательных чисел нужно при работе с массивом C к A[i] прибавлять |min|, а при обратной записи вычитать.

Анализ

В первых двух алгоритмах первые два цикла работают за } и }, соответственно; двойной цикл за . Об этом говорит сайт https://intellect.icu . В третьем алгоритме циклы занимают , , и , соответственно. Итого все три алгоритма имеют линейную временную трудоемкость . Используемая память в первых двух алгоритмах равна , а в третьем .

Квадратичный алгоритм сортировки подсчетом

Также сортировкой подсчетом называют немного другой алгоритм. В нем используются входной массив A и вспомогательный массив B для отсортированного множества. В алгоритме следует для каждого элемента входного массива A[i] подсчитать количество элементов меньших него {\displaystyle c_{1}} и количество элементов, равных ему, но стоящих ранее ( ). B[c] присвоить A[i]. Алгоритм устойчив.

SquareCountingSort
    for i = 0 to n - 1
        c = 0;
        for j = 0 to i - 1
            if A[j] <= A[i]
                c = c + 1;
        for j = i + 1 to n - 1
            if A[j] < A[i]
                c = c + 1;
        B[c] = A[i];

Анализ

Очевидно, временная оценка алгоритма равна , память .

Примеры реализации

Компонентный Паскаль[

Простой алгоритм.

PROCEDURE CountingSort (VAR a: ARRAY OF INTEGER; min, max: INTEGER);
  VAR
    i, j, c: INTEGER;
    b: POINTER TO ARRAY OF INTEGER;
BEGIN
  ASSERT(min <= max);
  NEW(b, max - min + 1);
  FOR i := 0 TO LEN(a) - 1 DO INC(b[a[i] - min]) END;
  i := 0;
  FOR j := min TO max DO
    c := b[j - min];
    WHILE c > 0 DO
      a[i] := j; INC(i); DEC(c)
    END
  END
END CountingSort;

Реализация на PascalABC.Net

 1 const
 2   n = 5;
 3   m = 12; // Максимальное значение всех элементов в a.
 4 
 5 var
 6   a: array [0..n] of integer;
 7   c: array [0..m] of integer; // Вспомогательный массив.
 8   i, j: integer; // Переменные, играющие роль индексов.
 9   k:integer;
10 begin
11   for i := 0 to n do 
12     a[i] := Random(m); // Заполнение массива.
13   for i := 0 to m do
14     c[i] := 0;  //Обнуление вспомогательного массива
15   for i := 0 to n do 
16     c[a[i]] := c[a[i]] + 1;
17   j := 0; // Обнуление j. Хороший стиль программирования обнулять все переменные изначально, поскольку не все компиляторы это делают автоматически.
18   for i := 0 to m do
19     for  k := 1 to c[i] do 
20     begin 
21         a[j] := i; 
22         Inc(j); 
23     end;
24   Writeln(a);
25 end.

Реализация на Python

 1 a=[]
 2 max_el=max(a)
 3 cnt=[0]*(max_el+1)
 4 
 5 for i in range(len(a)):
 6     cnt[a[i]]+=1
 7 
 8 pos=0
 9 for num in range(len(cnt)):
10     for i in range(cnt[num]):
11         a[pos]=num
12         pos+=1
13 print(a)

Вау!! 😲 Ты еще не читал? Это зря!

• Алгоритм сортировки
• O-большое
• Временная сложность алгоритма

Исследование, описанное в статье про сортировка подсчётом, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое сортировка подсчётом, сортировка подсчетом и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Качество и тестирование программного обеспечения. Quality Assurance.