Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

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



 

Для сортировки элементов исходного вектора А размерности 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;




Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.