Сортировка методом распределяющего подсчета

Понятно, что одна из важнейших работ в алгоритме построчного сканирования - сортировка. В связи с заведомо ограниченной разрешающей способностью растровых дисплеев (не более 2048) иногда целесообразно использовать чрезвычайно эффективный алгоритм сортировки методом распределяющего подсчета.

Для рассмотрения алгоритма предположим, что надо отсортировать числа, заданные в массиве с именем "Исходный_массив"; количество сортируемых чисел задается скаляром "Кол-во_чисел"; сортируемые числа J удовлетворяют условию:

0 Ј J < Max_число.

Для сортировки потребуются описания:

int Max_число; /* Верхняя граница значений */int *Повтор; /* Длина этого массива = Max_число */int Кол_чисел; /* Кол-во сортируемых чисел */int *Исходный_массив; /* Длина этого массива >= Кол_чисел */int *Результат; /* Длина этого массива >= Кол_чисел */int ii,jj, kk; /* Рабочие переменные */

1. Обнуляется служебный массив для подсчета числа повторений исходных кодов.

2. for (ii=0; ii<Max_число; ++ii) Повтор[ii]= 0;

1. Сортируемый массив просматривается и вычисляется количество раз повторений каждого числа:

4. for (ii= 0; ii < Кол_чисел; ++ii) {5. jj= Исходный_массив[ii];6. Повтор[jj]= Повтор[jj] + 1;7. }

1. Суммируется количество повторений каждого числа, так что значение Повтор[J] даст начальное расположение группы чисел, равных J, в отсортированном массиве:

9. jj= 0;10. for (ii=0; ii<Max_число; ++ii) {11. jj= jj + Повтор[ii];12. Повтор[ii]= jj;13. }

1. Просматривается исходный массив и числа из него заносятся в массив результатов той же длины. Индекс занесения числа J в массив результатов равен значению J-го элемента массива Повтор. После занесения числа J значение Повтор[J] уменьшается на 1:

15. for (ii= 0; ii < Кол_чисел; ++ii) {16. jj= Исходный_массив[ii];17. kk= Повтор[jj];18. Результат[kk]= jj;19. Повтор[jj]= Повтор[jj] - 1;20. }