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

l Фактыl :l

1. Потребуется два массива, входной A[ ] и выходной B[ ] , соответственно - формальные параметры функции, которая выполняет сортировку, а также их размерность - n .

void sort(int A[], int B[], int n)
{...}

2. Действие, связанное с подсчетом и перенесением элемента массива будет производиться для каждого из элементов массива A[ ], можно в любом порядке :

for (int i=0; i&#60n; i++)
{ подсчитать cnt для A[i] и перенести его в B[] }

3. Если для переменной cnt известен смысл - счетчик элементов, меньших текущего, то процесс перенесения значения из A[ ] в B[ ] можно записать, даже не зная способа его получения:

B[cnt]=A[i];

4. Для переменной-счетчика используется известный контекст :

for(cnt=0;...) { if(...) cnt++; }

5. Для подсчета количества значений, меньших A[i] нужно просмотреть в цикле все значения массива. Отдельный цикл требует нового индекса :

for (cnt=0,j=0; j&#60n; j++) if (A[j] &#60 A[i]) cnt++;

for (cnt=0,j=0; j&#60n; j++)
if (A[j] &#60 A[i] || A[j]==A[i] &#38&#38 j&#62i) cnt++;

Собранная из фрагментов программа будет иметь вид (не забывайте определения переменных) .

void sort(int A[], int B[], int n) // 1

{
for (int i=0; i&#60n; i++) // 2

{
for (cnt=0,j=0; j&#60n; j++) // 4,5,6

if (A[j] &#60 A[i] || A[j]==A[i] &#38&#38 j&#62i) cnt++;
B[cnt]=A[i]; // 3

}
}