Основы программирования (947332), страница 17
Текст из файла (страница 17)
Причем время сортировки не зависит от исходного порядка элементов.Метод вставки. Сортировку вставкамиРис. 4.14. Алгоритмможно описать следующим образом. В иссортировки выборомходном состоянии считают, что сортируемаяпоследовательность состоит из двух последовательностей: уже сортированной (она на первом шаге состоит из единственного - первого элемента) и последовательности элементов, которые еще необходимо сортировать. На каждом шаге из сортируемой последовательности извлекается элемент и вставляется в первую последовательность так, чтобы она оставалась сортированной. Поиск места вставки осуществляют с конца, сравнивая вставляемыйэлемент а; с очередным элементом сортированной последовательности а:.Если элемент aj больше а:, его вставляют вместо aj^.], иначе сдвигают а:вправо и уменьшают] на единицу. Поиск места вставки завершают, если элемент вставлен или достигнут левый конец массива.
В последнем случае элемент aj вставляют на первое место (рис. 4.15).Разрабатывая алгоритм, избавимся от проверки достижения начала массива. Прием, позволяющий отменить эту проверку, называется «установкойбарьера». С использованием этого приема проверка организуется так, чтобы99Часть 1. Основы алгоритмизации и процедурное программирование( Начало J1 7.8 -6.3 5.81.28.4/4.5 1/Ввод"> ^">7/i:=2,n,l1-йпроход2-йпроход1.2ГГл .-6.31.231ГГЛ^о\/5.8-6.35.87.84.5B:=A[i]А[0]:=ВMJ ШjH-lГГл4.57.8MJ ШA[i]>B нетЖ.AD+1]:=AD]j:=j.ln-lЗ-йпроход-6.3 1.2 4.55.8%%Ж1 Шп-2ЛА0+1]:=В4-йпроход-6.31.24.5$Л\1Л\ЬА\Шп-3/[-6.31.24.55.87.88.4 1Рис. 4.15.
Сортировка вставкамиВыводА(п)Г КонецУ/jРис. 4.16. Схемаалгоритма сортировки вставкамииз цикла поиска места вставки в любом случае происходил выход по первому условию. Для этого достаточно поместить вставляемый элемент передпервым элементом массива, как элемент с индексом 0. Этот элемент и станетестественным барьером для ограничения выхода за левую границу массива.Алгоритм сортировки вставками приведен на рис. 4.16. Ниже приведентекст программы, реализующей данный алгоритм.Program sort2;Var a:arrayfO.,20J of real; В .real;ij\n:mteger;BeginWriteLn(*Введите количество чисел n<=20,');1004, Структурные типы данныхReadLn(n);WriteLnCВведите массив.');for /V=7 to п do Read(a[i]);ReadLn;for i:-2 to n do {начиная со второго элемента до конца массива}beginB:-a[i]; {запоминаем i-й элемент}afOJ:=^B; {этот же элемент записываем в а[0] - это барьер}j:=i'l;{индекс i запоминаем в j}while B<a[/J do {пока очередной рассматриваемый элементбольше i-ro элемента}begin^//"^^/•'"^//У/ {сдвигаем элемент}у;=у-7;{уменьшаем j на 1}end;а[/+1]:=В;{как только найдено место, туда записывается В}end;WriteLnC Отсортированный массив:');for i:=l to п do Write(a[i]:6:2);WriteLn;EndОценим временную сложность данного метода, также определив количество операций сравнения.Для поиска места i-ro элемента каждый раз потребуется выполнить от 1до i-1 операций сравнения, т.е.
в среднем i/2 операций сравнения. Значение iизменяется от 2 до п, т.е. выполняется п-1 проход, в каждом из которых происходит в среднем от 1 до п/2 сравнений. Таким образом, суммарно в среднем для решения задачи требуется выполнить (п-1)(п/2 + 1)/2 = (п^ + п - 2)1Аопераций сравнения. Откуда вычислительная сложность метода в среднемтакже равна О^рСп^), хотя время выполнения примерно в два раза меньше,чем у предыдуш.его метода.
Интересно, что в данном случае вычислительнаясложность зависит от исходного расположения элементов массива.Так, в лучшем случае, когда массив уже упорядочен, поиск места вставки требует одного сравнения для каждого элемента, и количество сравненийравно п-1. Соответственно, вычислительная сложность равна 0^(n).В худшем случае, если элементы массива в исходном состоянии расположены в обратном порядке, поиск места вставки для каждого элемента потребует: 1, 2, 3, ..., п-1 сравнения, следовательно, всего потребуется п(п-1)/2операций сравнения, т. е. время выполнения программы примерно совпадетсо временем программы, реализующей метод выбора. Значит вычислительная сложность в худшем, так же как в среднем, равна Oj^(n2).Таким образом, за счет ускорения сортировки в лучших случаях данныйметод имеет лучшие временные характеристики, чем предыдущий.101Часть 1.
Основы алгоритмизации и процедурное программированиеМетод обменов» Алгоритм прямого обмена основывается на сравнениипары соседних элементов. Если расположение элементов не удовлетворяетусловиям сортировки, то их меняют местами. Сравнения и перестановкипродолжают до тех пор, пока не будут упорядочены все элементы. Определить, что элементы упорядочены, можно, считая количество выполненныхперестановок: если количество перестановок равно нулю, то массив отсортирован (рис.
4.17).Простейший алгоритм сортировки с помощью обмена представлен нарис. 4.18. Ниже приведена программа, реализующая данный алгоритм.7.8 -6.3 5.8 1.2 8.4 4.5к1-йпроход-6.35.81.22-йпроход-6.31.25.8 4.5 7.8п-13-йпроход-6.3 1 1.2 1 4.5 1 5.8 1 7Л 1 8.4 1 1 1 17.8 4.5 8.4ШГТлШ П}^-—^кп-24-йпроходк-6.3 1 1.2 1 4.5 1 5.8 ( 1Л { 8.4 | 1 0 1п-З-6.3 1.2 4.5 5.8 7.8 8.4Рис. 4.17. Сортировка обменом102Рис 4.18. Схема алгоритмасортировки обменом4.
Структурные типы данныхProgram ex;Var а: array[L.20] of Real;ij,nj,k: integer;b:real;BeginWriteLn(*Введите размер массива N< =20');ReadLn(n);for i := 1 ton do Read(a[i]);ReadLn;WriteLnCИсходный массив:');for i := J to n do Write(a[i]:7:2);WriteLn;k:-l; {количество перестановок, начальное значение не равно О }i;=7; {номер очередного просмотра, в начале равен 1}while koQ do {пока есть перестановки}beginк:-0; {обнуляем количество перестановок}forj:-l to п4 do {цикл сравнения соседних элементов}if (^Ш^^О'^Ч ^f^^^ {если предыдущий элемент больше, то}begin{осуществляем перестановку}b:=a[j];a[i+lj:^b;к:=к-^1; {счетчик перестановок увеличиваем на 1}end;i;=/+i; {увеличиваем номер просмотра на 1}end;WriteLn('Отсортированный массив *);for i := J to п do Write(a[i]:7:2);WriteLn;WriteLnC Количество проходов \ i:3);EndОценим вычислительную сложность данного метода. Очевидно, что онасильно зависит от исходного расположения элементов массива.
Так, в лучшем случае, если массив был уже отсортирован, потребуется выполнить п-1сравнение для проверки правильности расположения элементов массива, т. е.вычислительная сложность в лучшем 0^(п).В худшем случае, если массив отсортирован в обратном порядке, будетвыполнено п-1, п-2, ...1 операций сравнения, т. е. всего (п2-п)/2 операцийсравнения, следовательно, вычислительная сложность в худшем определяется как Ох(п2).Выполнить усредненную оценку данного метода достаточно сложно, таккак в отличие от предыдущих случаев зависимость времени выполнения отколичества неправильно стоящих элементов не является линейной. Например, два элемента, стоящие на своем месте в начале массива, практически не1034. Структурные типы данныхПроверка и удаление строк:к:=0Для i:=l, п, 1Определение максимального элемента max i-й строки.Если тах?^В,то к:=к+1Перемещение i-й строки на к-е местовсе-еслиВсе-циклВсе.Определение максимального элемента строки - уже известная нам операция (см.
пример 4.1).Перемещение строки выполняется поэлементно.Перемещаем i-ю строку на к-е место:Д л я ] = 1,т, 1A[kJ]:=A[ij]Все-цикл.Все.Ниже представлен полный текст программы.Program ex;Var а: arrayfI..JO,LJOJ of integer;В, max, n, m, k, i,j: integer;BeginWriteLnCВведите размеры матрицы n,m<=10');ReadLn(n,m);WriteLnCВведите \n:4,' строк no \m:4,' элементов ');for i:'=l to n dobeginforj:=l to m do ReadfafiJJJ;ReadLn;end;WriteLnCВведите значение В:');ReadLn(B);WriteLnCИсходный массив');for i:=l to n dobeginforj:=l to m do Write(a[iJ]:4);WriteLn;end;k:=0;{количество остающихся строк}105Часть 1.
Основы алгоритмизации и процедурное программированиеповлияют на время сортировки, а два элемента, стоящих на своем месте вконце массива, вызовут ее досрочное завершение. По результатам тестирования можно считать, что в среднем этот метод сортировки требует примернов два раза меньше времени, чем предыдущий. Вычислительная сложность всреднем данного метода О^рСп^).Примечание. По материалам данного раздела можно сделать ошибочный вывод, что всеметоды сортировки в среднем имеют вычислительную сложность 0(п2). Методы сортировки,рассмотренные в данном разделе, не являются самыми быстрыми, они просто самые простыеи потому используются чаще всего.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
