КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Сортировка методом прямого включения
Сортировка методом прямого включения, так же как и сортировка методом простого выбора, обычно применяется для массивов, не содержащих повторяющихся элементов. Сортировка методом прямого включения, как и все описанные выше, производится по шагам. На k - м шаге считается, что часть массива, содержащая первые k-1 элементов, уже упорядочена, то есть а [1] ≤ а [2] ≤... ≤ a [k-1]. Далее необходимо взять k - й элемент и подобрать для него такое место в отсортированной части массива, чтобы после его вставки упорядоченность не нарушалась, то есть надо найти такое j (1 ≤ j ≤ k -1), что а [j] ≤ a[k] < a[j+1]. Затем вставить элемент а [k] на найденное место. С каждым шагом отсортированная часть массива увеличивается. Для выполнения полной сортировки потребуется выполнить n-1 шаг. Рассмотрим этот процесс на примере. Пусть требуется отсортировать массив из 10 элементов по возрастанию методом прямого включения
1 - й шаг 13 6 8 11 3 1 5 9 15 7 Рассматриваем часть массива из одного эле- мента (13). Нужно вставить в нее второй элемент массива (6) так, чтобы упорядочен- ность сохранилась. Так как 6 < 13, вставляем 6 на первое место. Отсортированная часть массива содержит два элемента (6 13).
2 - й шаг 6 13 8 11 3 1 5 9 15 7 Возьмем третий элемент массива (8) и под- берем для него место в упорядоченной части массива. 8 > 6 и 8 < 13, следовательно, его нужно вставить на второе место. 3 - й шаг 6 8 13 11 3 1 5 9 15 7 Следующий элемент - 11. Он записывается в упорядоченную часть массива на третье место, так как 11 > 8, но 11 < 13. 4 - й шаг 6 8 11 13 3 1 5 9 15 7 Далее, действуя аналогичным образом, определяем, что 3 необходимо записать на
первое место. 5 - шаг 3 6 8 11 13 1 5 9 15 7 По той же причине 1 записываем на первое место. 6 - шаг 1 3 6 8 11 13 5 9 15 7 Так как 5 > 3, но 5 < 6 то место 5 в упоря- доченной части - третье.
7 - шаг 1 3 5 6 8 11 13 9 15 7 Место числа 9 - шестое. 8 - шаг 1 3 5 6 8 9 11 13 15 7 Определяем место для предпоследнего элемента 15. Оказывается, что этот эле- мент массива уже находится на своем месте.
9 - шаг 1 3 5 6 8 9 11 13 15 7 Осталось подобрать подходящее место для последнего элемента (7).
1 3 5 6 7 8 9 11 13 15 Массив отсортирован полностью.
Сейчас можно коротко описать фрагмент алгоритма сортировки методом прямого включения: For k: = 2 To n Do { так как начинам сортировку с поиска подходящего места для a[2], i изменяется от 2 до n } Begin x: = a[k]; ‘вставить x на подходящее место в a[1],..., a[k] ‘ End; Осталось ответить на вопрос, как осуществить поиск подходящего места для элемента x. Поступим следующим образом: будем просматривать элементы, расположенные левее x (то есть те, которые уже упорядочены), двигаясь к началу массива. Нужно просматривать элементы a[ j ], j изменяется от k-1 до 1. Такой просмотр должен закончиться при выполнении одного из следующих условий: · найден элемент a[j] < x, что говорит о необходимости вставки x между a[j-1] и a[j]. · достигнут левый конец упорядоченной части массива, следовательно, нужно вставить x на первое место. До тех пор, пока одно из этих условий не выполнится, будем смещать просматриваемые элементы на первую позицию вправо, в результате чего в отсортированной части будет освобождено место под x.
Программа сортировки методом прямого включения:
program n3; { Сортировка по убыванию } const n=5; type ar=array [1..n] of integer; var i:integer; a:ar;
procedure sorting3(var a:ar); var i,j,x,k:integer; begin for k:=2 to n do begin x:=a[k]; j:=k-1; while (j>0)and(x>=a[j]) do begin a[j+1]:=a[j]; dec(j); end; a[j+1]:=x; end; end; begin writeln('Введите исходный массив:'); for i:=1 to n do read(a[i]);
sorting3(a); writeln('Отсортированный массив:'); for i:=1 to n do write(a[i],' '); writeln; end.
Дата добавления: 2014-11-09; Просмотров: 378; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |