Вы здесь

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

Исходный код на C++: 

Теория

Сортировка подсчётом предполагает использование выходного массива. Идея алгоритма заключается в том, что мы просматриваем входной массив и сравниваем in[i] и in[j] элементы массива. Если in[i]>in[j], то увеличиваем значение индекса на 1 .Индекс определяет позицию элемента в выходном массиве. Приведём пример. Дан входной массив чисел: 5,6,12,89,56,-5,6,7, количество элементов в массиве 8. Создаём выходной массив размерностью равной входному (т.е. 8) (рис.1).

Создаём выходной массив
Рис. 1 Сортировка подсчётом. Шаг 0.

На первом шаге сортировки переменная i=0, а j пробегает по всем элементам массива in. Если in[i]>in[j], то увеличиваем индекса на 1. После первого шага алгоритма 5 получит позицию один в выходом массиве, так как нумерация элементов начинается с 0 (рис.2).

После первого шага работы алгоритма
Рис. 2 Сортировка подсчётом. Шаг 1.

На втором шаге алгоритма переменная i=1, а j пробегает по всем элементам массива in. В входном массиве два элемента равные 6, поэтому мы должны это учитывать. Иначе два элемента получат одинаковую позицию в выходном массиве, что приведёт к неправильной работе алгоритма. Введём дополнительное условие, которое обеспечит корректную работу алгоритма. Если in[i] элемент равен in[j] и при этом i<j, то индекс увеличиться на 1. После добавления условия «первая»6 (in[1]) получает позицию 3 в выходном массиве (рис. 3), а «вторая»6 (in[6]) получает позицию 2.

После второго шага работы алгоритма
Рис. 3 Сортировка подсчётом Шаг 2.

Продолжая итерационный процесс, мы получим отсортированный массив. Трудоёмкость алгоритма- n*n/2.

Программная реализация

void sort_podchet(int count,double *in,double *out)
{
int i,j,k;
for(i=0;i &lt; count;i++)
{
for(j=k=0;j &lt; count;j++)
if(in[j] &lt in[i] ||(in[i]==in[j] && i &lt; j))k++;
out[k]=in[i];
}
}