Реферат «Сортировка массива методом вставки» по Информатике (Попов Д. И.)

Кирилл Николоев вт, 29.03.2016 21:00

Содержание: 1. Бинарные вставки 2. Двухпутевые вставки 3. Вставки одновременно нескольких элементов 4. Вставки с убывающим шагом (метод Шелла) 5. Вставки в связанный список 6. Вставки в несколько связанных списков

Методы вставки. Алгоритм простых вставок. {сортировка вставкой} procedure Inser(var item: DataArray; count:integer); var i, l: integer; x: DataItem; begin for i := 2 to count do begin x := item[i]; j := i-1;

while (x0) do begin item[j+1] := item[j]; j := j-1; end; item[j+1] := x; end; end; Ниже описан основной алгоритм простых вставок, который порождает несколько модификаций, используемых в заданиях. Алгоритм использует прием, которым пользуются игроки в карты при сортировке только что розданной колоды: очередная карта вставляется между уже упорядоченными ранее. Описание алгоритма простых вставок. Файл, подлежащий сортировке, в общем случае состоит из элементов-записей, включающих информационную часть и ключи, по которым производится упорядочение по возрастанию. Поскольку информационная часть почти не влияет на процесс сортировки, будем предполагать, что файлы, используемые в примерах, состоит только из элементов-ключей, а информационная часть записи отсутствует. Здесь k[1], k[2], , k[N] - ключи, по которым производится упорядочение файла. X,i,j - рабочие переменные.

Для примера возьмем файл, состоящий из 8 элементов: Исх.файл.: 503 87 512 61 908 170 897 275 Алгоритм будет преобразовывать его следующим образом: j=2. Исх : 503 87 X=87 Рез : °87 503 j=3 : 87 503 °512 X=512

j=4 : °61 87 503 512 X=61 j=5 : 61 87 503 512 °908 X=908 j=6 : 61 87 °170 503 512 908 X=170 j=7 : 61 87 170 503 512 °897 908 X=897 j=8 : 61 87 170 °275 503 512 897 908 X=275 Время работы алгоритма t примерно оценивается формулой:

t=a*N + b*N, где a,b - неизвестные константы, зависящие от программной реализации алгоритма. Модификации алгоритма простых вставок. 1. Бинарные вставки {сортировка бинарными вставками} for i:=2 to n do

begin r:=i; l:=i; while (la[i] then l:=k+1; else r:=k; end; k:=r; x:=a[i]; for m:=i downto k+1 do a[m]:=a[m-1]; a[k]:=x; end; Для ускорения числа сравнений при поиске места, в которое нужно вставить элемент X, можно использовать логарифмический поиск. Это означает, что сначала Х сравнивается с элементом k[j/2], затем, в зависимости от результата сравнения, с элементом, лежащим посередине между 1 и j/2 или посередине между j/2+1 и j и т.д. . При этом число сравнений для каждого j равно примерно log(j). Число пересылок элементов при этом не изменяется и остается примерно равным N/4. Время работы алгоритма t примерно оценивается формулой:

t=a*N + b*N + c*N*logN, где a,b,c - неизвестные константы, зависящие от программной реализации алгоритма, log - логарифм по основанию 2. 2. Двухпутевые вставки Число пересылок можно сократить примерно в 2 раза до N/8, если допустить сдвиги элементов не только вправо, но и влево. Для выходного файла резервируется место в памяти, равное 2N+1 ,где N - число элементов в исходном файле. Первый элемент пересылается в середину выходного файла. В дальнейшем элементы выходного файла сдвигаются вправо или влево в зависимости от того, в какую сторону нужно сдвигать меньше элементов. Файл из предыдущего примера будет сортироваться следующим образом.

Скачать файлы

Похожие документы