Линейный выбор с подсчетом

Для сортировки элементов исходного вектора А размерности n, нужно сформировать вектор счетчиков S размерности n, каждый элемент которого будет показывать, в какой позиции должен стоять соответствующий элемент вектора А в упорядоченном списке.

На первом этапе в вектор счетчиков заносятся единицы. Для формирования вектора счетчиков нужно n-1 раз просмотреть элементы исходного вектора A.

При первом просмотре для первого элемента вектора A подсчитывается количество меньших элементов во всем векторе и это количество заносится в счетчик первого элемента, в счетчики элементов, больших первого, добавляются единицы.

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

Перемещая элементы исходного вектора A в полученный вектор B в соответствии со значениями вектора счетчиков S, получим упорядоченный исходный вектор B.

Просмотр	Исходный вектор А	Вектор счетчиков S
1-ый	2 4 8 5 6 1	1 1 1 1 1 1 + 1 1 1 1 1 2 2 2 2 2 1
2-ой	2 4 8 5 6 1	2 2 2 2 2 1 + 1 1 1 1 2 3 3 3 3 1
3-ий	2 4 8 5 6 1	2 3 3 3 3 1 + 3 2 3 6 3 3 1
4-ый	2 4 8 5 6 1	2 3 6 3 3 1 + 1 1 2 3 6 4 4 1
5-ый	2 4 8 5 6 1	2 3 6 4 4 1 + 1 2 3 6 4 5 1

Таким образом, сформированный вектора счетчиков показывает, что первый элемент вектора A должен стоять в упорядоченном списке на втором месте, второй элемент вектора A – на третьем, третий элемент – на последнем и т.д.

For i:=1 to n do {инициируем вектор счетчика}

S[i]:=1;

For i:=1 to n-1 do {формируем вектора счетчика}

Begin

k:=0; {количество меньших элементов для i-го элемента}

For j:=i+1 to n do

If A[i]<A[j] then S[j]:=S[j]+1

{в счетчики больших элементов добавляем единицы}

else k:=k+1;

S[i]:=S[i]+k;

end;

{формируем вектор B в соответствии со значениями вектора счетчика}

For i:=1 to n do

Begin

r:=S[i];

B[r]:=A[i];

end;