Внутренняя сортировка данных методом подсчета. Эффективность данного алгоритма. Привести фрагмент программы, поясняющий данный алгоритм

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов.

Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза..

Оценим эффективность сортировки подсчетом по количеству сравнений. Так как мы сравниваем каждый элемент с каждым элементом массива, то имеем N*N сравнений. Эффективность алгоритма C=N*N=Θ(N²), т.е. сортировка подсчетом имеет квадратичную сложность. Множитель N² свидетельствует о том, что алгоритм неэффективен при большом N, т.к. при удвоении числа элементов массива количество сравнений увеличится в 4 раза. Но он очень прост в реализации.

Независимо от отсортированности массива, количество перестановок равно длине массива N. То есть эффективность алгоритма по перестановкам имеет линейную сложность.

Число перестановок: min=0, max= N², med= N²/2

Число сравнений: N²

Пример

К 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703

С 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

С1 6 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1

К1 сравнивается с остальными, если больше Сn, то 1, если меньше – 0, потом количество нулей вписывается в С1.

Считаем, сколько элементов меньше первого элемента массива (503), затем – сколько элементов меньше второго числа(087), и т.д. Число 503 по значению превышает только шесть чисел. и.т.д

С2 6 1 2 0 2 1 2 1 1 1 1 2 2 2 2 2

С3 6 1 6 0 3 1 3 1 2 1 1 2 3 3 3 3

С4 6 1 8 0 4 2 4 …

…

С15 6 1 8 0 15 3 14 4 10 5 2 7 9 11 13 12

Фрагмент программы:

For (i=0; i<n-1; i++)

For (i=i+1; j<n; j++)

{ if (k[i]>k[j]) c[i]++;

Else c[j]++;

}