Информатика и технология программирования

         

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


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

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++;

6. Уточнение. Если в массиве есть два одинаковых значения, то они попадут в одну и ту же ячейку выходного, поскольку счетчики их будут одинаковы. Следующая же ячейка окажется пуста. Это можно исправить, если, например, подсчитывать также и равные значения, но расположенные справа от текущего. Смысл фразы " справа от i- го" выражается соотношением j&#62i. Тогда фрагмент подсчета примет вид :


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


}
}


Путем сравнения всех пар элементов массива для каждого из них подсчитывается количество элементов, меньших его. Это дает новое местоположение этого элемента в выходном массиве. Трудоемкость алгоритма -n*n/2. Текст ищите в " Вопросах без ответов " .



Содержание раздела