Методические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "




НазваниеМетодические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "
страница6/19
Дата публикации28.09.2013
Размер1.39 Mb.
ТипМетодические указания
vbibl.ru > Информатика > Методические указания
1   2   3   4   5   6   7   8   9   ...   19


Метод Шелла

Эффективным усовершенствованием метода вставки является метод Шелла – прямое включение с убывающим шагом.

Метод состоит в том, что упорядочиваемая таблица разбивается на группы элементов (записей), каждая из которых упорядочивается методом вставки. В группу входят не непосредственные соседи, а записи, отстоящие друг от друга на заданное расстояние (шаг группы). Таким образом, группой таблицы называют такую совокупность элементов, номера которых образуют арифметическую прогрессию с разностью h.

В начале процесса упорядочения выбирается первый шаг группы, который Шелл предложил брать в виде h1=[n/2], где n – размер таблицы. Однако Хиббард показал, что сортировка дает лучшие результаты, если первый шаг будет степенью двойки: h1=2k-1, где 2<=n <2k+1. Последующие шаги определяются по формуле: hi = [hi-1/2].

Таким образом, при каждом новом просмотре таблицы расстояние между элементами группы уменьшается, количество же элементов в группе увеличивается. На последнем просмотре шаг становится равным 1.

На ранних просмотрах элементы совершают большие скачки к нужным позициям, а не передвигаются на одну позицию, как в методе вставки. Это позволяет сократить число повторных сравнений и обменов на более поздних просмотрах. На последнем просмотре таблицы записи будут расположены близко к своим позициям, и, следовательно, не потребуют значительных перемещений при окончательном размещении.

Рассмотрим подробнее алгоритм метода.

После выбора h1 методом вставки упорядочиваются группы, содержащие элементы с номерами позиций i, i+h1, i+2*h1, ..., i+mi*h1. При этом i=1,2,...,h1 (не более h1); mi – наибольшее целое, удовлетворяющее неравенству i+mi*h1 <= n.

Затем выбирается шаг h2 (h21), и упорядочиваются группы, содержащие элементы с номерами позиций i, i+h2, ..., i+mi*h2. Эта процедура со все уменьшающимися шагами продолжается до тех пор, пока очередной шаг hl станет равным единице (h1>h2>...>hl). Этот последний этап представляет собой упорядочение всей таблицы методом вставки. Но так как исходная таблица упорядочивалась отдельными группами с последовательным объединением этих групп, то общее количество сравнений значительно меньше, чем n2/4, требуемое при методе вставки. Число операций сравнения пропорционально n (log2n)2 .

Рассмотрим пример сортировки методом Шелла:

^

Номера позиций упорядочиваемой таблицы


Шаг

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15




6

1

3

15

8

14

13

11

10

4

9

2

5

12

7

h=7

6

1

3

15

8

14

13

7

10

4

9

2

5

12

11




6

1

3

15

8

14

13

7

10

4

9

2

5

12

11




6

1

3

15

8

14

13

7

10

4

9

2

5

12

11




6

1

3

9

8

14

13

7

10

4

15

2

5

12

11




6

1

3

9

2

14

13

7

10

4

15

8

5

12

11




6

1

3

9

2

5

13

7

10

4

15

8

14

12

11




6

1

3

9

2

5

12

7

10

4

15

8

14

13

11

h=3

4

1

3

6

2

5

9

7

10

12

15

8

14

13

11




4

1

3

6

2

5

9

7

10

12

13

8

14

15

11




4

1

3

6

2

5

9

7

8

12

13

10

14

15

11

h=1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15





"Быстрая" сортировка (обменная сортировка с разделением)
"Быстрая" сортировка является одним из лучших методов внутренней сортировки и весьма эффективна для больших таблиц (предложена Ч. Хоаром). На каждом шаге данного метода таблица с помощью разделяющего элемента делится на две подтаблицы таким образом, что в левой подтаблице размещаются записи, ключи которых меньше или равны ключа разделяющего элемента, а в правой – больше или равны. Аналогичное разделение применяется к каждой из полученных подтаблиц и повторяется до тех пор, пока все записи не будут установлены на их конечные позиции. Среднее число сравнений для данного метода составляет n log2(n).

Существуют два варианта "быстрой" сортировки: в качестве разделяющего элемента могут быть взяты ключ первой записи таблицы или ключ средней записи.
^ 1. Рассмотрим первый шаг "быстрой" сортировки, взяв в качестве разделяющего элемента ключ первой записи таблицы. Используются два индекса i и j с начальными значениями границ таблицы (i=1, j=n). Сравниваются ключи K[i] и K[j], и, если перестановка записей таблицы не требуется, то j уменьшается на 1 и сравнение продолжается. В том случае, когда K[i] > K[j], записи R[i] и R[j] меняются местами. Затем сравниваются записи с i, увеличиваемым на 1, и фиксированным j до тех пор, пока не возникнет следующая перестановка. Далее j снова будет уменьшаться на 1, а i оставаться фиксированным. Процесс выполняется до тех пор, пока i. В итоге выполнения первого шага разделяющий элемент станет на свою конечную позицию, а таблица разобьется на две подтаблицы, элементы которых имеют индексы в интервалах [1, (i-1)] и [(i+1), n].
После каждого шага подтаблица разбивается на две части, одна из которых обрабатывается, а границы второй должны быть сохранены для дальнейшей обработки. Среднее число сравнений для данного метода составляет n log2(n).
В качестве примера рассмотрим записи со следующими ключами:

42 23 74 11 36 58 94
Ниже приведена последовательность перестановок (обменов) при перемещении записи с ключом 42 на ее конечную позицию (первый шаг сортировки). Ключи, значения которых сравниваются, подчеркнуты:


42

23

74

11

36

58

94

42

23

74

11

36

58

94

42

23

74

11

36

58

94

36

23

74

11

42

58

94

36

23

74

11

42

58

94

36

23

42

11

74

58

94

36

23

11

42

74

58

94


В результате исходная таблица разбита на две подтаблицы: [36, 23, 11] с границами элементов l=1, r=(i-1) и [74, 58, 94] с границами l=(i+1), r=n. Запись с ключом 42 в дальнейшей сортировке не участвует.
Для продолжения сортировки таблицы нужно применить этот процесс к получившимся двум частям, затем к частям частей и так до тех пор, пока каждая из частей не будет состоять из одного элемента. Запоминать специально границы разделенных частей не нужно, так как современные системы программирования позволяют реализовывать рекурсивные процедуры.

Рекурсивная процедура "быстрой" сортировки с первым разделяющим элементом может выглядеть так:
Рrocedure SORT_1 (l, r: integer);

var i,j:integer;

. . . . . . . . . . . . . . . . .

begin

i:=l; j:=r;

{процесс разделения}

. . . . . . . . . . . . . . . . . . . .

if (i-1)>l then SORT_1 ( l, i-1 );

if (i+1)<r then^ SORT_1 ( i+1, r );

end;
2. Возьмем в качестве разделяющего элемента ключ средней записи таблица и обозначим его через К. На первом шаге сортировки X=K[n/2].
Сравниваем с Х сначала ключи К[i] записей, расположенных слева от X. Если K[i], то i:=i+1 (i=1 – начальное значение) и сравнения продолжаются. Как только K[i]>=X, i фиксируется, и начинается просмотр ключей справа от X. Если K[j]>X, то j:=j-1 (j=n – начальное значение) и сравнения продолжаются. При K[j]<=X фиксируется j. Как только i и j зафиксированы, происходит обмен местами записей R[i] и R[j] и изменение значений индексов (i:=i+1, j:=j-1).
Процесс сравнения ключей с X и обмена записей продолжается до тех пор, пока i<=j. При i>j первый шаг алгоритма завершается, и таблица становится разделенной на две подтаблицы: левую - с ключами, меньше или равными Х, и правую – с ключами, больше или равными Х. Элементы этих подтаблиц имеют индексы в интервалах [l, j] и [i, r]. Далее метод разделения применяется к полученным подтаблицам, каждая из которых также делится на две части.
Сортировка продолжается до тех пор, пока каждая из подтаблиц не будет состоять из одного элемента.

В качестве примера рассмотрим записи со следующими ключами:

16 22 89 99 85 18 87 13 90 50

Разделяющий элемент X= K[5]= 85; i= 1, j= 10 (первый шаг сортировки). Разделяющий ключ и ключи элементов, требующих перестановки, подчеркнуты:



1

2

3

4

5

6

7

8

9

10




16

22

89

99

85

18

87

13

90

50

i=3, j=10- обмен

16

22

50

99

85

18

87

13

90

89

i=4, j=8- обмен

16

22

50

13

85

18

87

99

90

89

i=5, j=6- обмен

16

22

50

13

18

85

87

99

90

89

i=6, j=5, i > j -

конец шага


В результате выполнения первого шага сортировки заданная таблица будет разбита на две подтаблицы: [16, 22, 50, 13, 18] с границами элементов l=1, r=j и [85, 87, 99, 90, 89] с границами l=i, r=n.
Рассмотренную разновидность метода "быстрой" сортировки также нужно реализовать методом рекурсии:
Рrocedure SORT_sr (l, r: integer);

var i,j:integer;

. . . . . . . . . . . . . . . . .

begin

{процесс разделения}

. . . . . . . . . . . . . . . . . . . .

if j>l then SORT_sr ( l, j );

if i<r then SORT_sr ( i, r );

end;
Метод простого двухпутевого слияния (сортировка слиянием)
В основе сортировки таблицы методом слияния лежит процедура слияния двух упорядоченных таблиц. Эти таблицы должны быть объединены таким образом, чтобы получилась одна упорядоченная таблица. Пусть имеются таблицы А и В, упорядоченные по возрастанию значений ключей. Слияние заключается в поочередной пересылке элементов из таблиц А и В в зону формирования С. Порядок пересылки в зону формирования зависит от результата попарного сравнения ключей таблиц А и В.
Сущность метода простого двухпутевого слияния состоит в том, что упорядочиваемая таблица на каждом шаге сортировки представляется равными упорядоченными группами элементов, которые попарно сливаются, образуя новые группы, содержащие вдвое больше элементов (на первом шаге группы состоят из одного элемента). От шага к шагу количество групп уменьшается вдвое, пока не будет получена одна упорядоченная группа.
Особые случаи метода:

1) если число групп, сформированных на некотором шаге сортировки, нечетно, то последняя (непарная) группа не участвует в процессе слияния на данном шаге;

2) длины сливаемых групп одинаковы, кроме, может быть, последней группы.
Процедура слияния двух групп имеет такие параметры:

^ TAB – имя сортируемой таблицы;

n – длина таблицы (количество записей);

i1, i2 – начальные индексы сливаемых групп;

l1, l2 – длины сливаемых групп;

h – шаг слияния;

PS – поле слияния (дополнительный объем памяти).



Рассмотрим пример сортировки слиянием таблицы со следующими ключами:

11 74 42 23 65 58 94 36 87 99 34 67



Первоначально шаг слияния равен 1, затем он удваивается при переходе к каждому последующему шагу сортировки (h=2*h).

На любом шаге сортировки первые две сливаемые группы должны иметь такие параметры: i1=1, l1=h, i2=i1+h, l2=h (l2 может быть равным (n-i2+1) – для последней группы таблицы).

При переходе к слиянию следующих двух групп параметры изменяются следующим образом: i1=i1+2*h, l1=h, i2=i1+h, l2=h или, возможно, l2=n-i2+1.

Сортировка продолжается до тех пор, пока h<n.
Рассмотренный метод сортировки двухпутевым слиянием весьма эффективен. Поскольку при сортировке нужно выполнить log2n шагов, то необходимое суммарное число сравнений равно, примерно, n*log2n. Одним из недостатков данного метода является требование дополнительного резерва памяти, равного объему исходной таблицы
^ Метод естественного слияния (сортировка слиянием)
Метод простого двухпутевого слияния никак не учитывает тот факт, что в таблице могут изначально находиться упорядоченные последовательности записей длиной m и l, которые можно сразу объединить в одну упорядоченную группу длиной (m+l) (при двухпутевом слиянии эти упорядоченные последовательности разорвутся, и их элементы будут включены в разные группы).

Сортировка, при которой сливаются рядом стоящие упорядоченные группы произвольной длины, называется естественным слиянием. Цель естественного слияния – исключить лишние просмотры.

Процедура слияния двух групп такая же, как и в методе простого слияния, но длины l1 и l2 сливаемых групп нужно каждый раз подсчитывать.
На первом шаге сортировки длины групп определяются сравнением ключей двух рядом стоящих записей. При этом нужно составить массив длин упорядоченных групп. Элементы этого массива будут использованы для вычисления длин групп на последующих шагах сортировки.
Рассмотрим пример: сортируется таблица с ключами 11, 15, 23, 14, 50, 58, 60, 12, 6, 16, 20, 5.

Вспомогательный массив длин групп :
1) 3 2) 7 3) 11

4 4 1

1 1

3

1
^ Определение операции поиска
Поиском называется операция выделения из множества записей подмножества, записи которого удовлетворяют заранее поставленному условию. Возможны следующие критерии поиска:

  • по совпадению,

  • по интервалу,

  • по близости,

  • по арифметическому условию,

  • по семантическому условию,

  • по нескольким условиям.

Алгоритмы указанных разновидностей поиска можно получить из алгоритма поиска по совпадению, при котором задается поисковый признак (ключ поиска) и требуется выделить все записи, удовлетворяющие ему.

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

Число сравнений ключей (длина поиска), требующееся для нахождения определенной записи, при последовательном поиске равно, в среднем, (n+1)/2, максимальная длина поиска (в наихудшем случае) равна n. Очевидно, что затраты времени на такой поиск весьма существенны, поэтому он используется в основном для небольших неупорядоченных таблиц.

Для уменьшения времени поиска нужно сначала упорядочить таблицу, а затем использовать методы, более эффективные по сравнению с последовательным поиском.
Существует группа методов поиска, в основе которых лежит деление таблицы на части. На практике наибольшее распространение получил метод деления на две части (подтаблицы) - дихотомический (бинарный, двоичный, логарифмический) поиск. В зависимости от результата сравнения ключа срединной записи и ключа поиска одна из подтаблиц отбрасывается, и поиск продолжается в другой подтаблице. В процессе поиска участвуют границы рассматриваемых подтаблиц: ng нижняя граница индекса, vgверхняя граница индекса. Первоначально ng=1, vg=n.
Дихотомический поиск по совпадению
Пусть таблица упорядочена по возрастанию значений ключа
(K[1] <=K[2]<=...<=K[n]), и нужно найти запись с ключом KL. Предполагается, что в таблице может быть только одна запись с заданным ключом (или ни одной).

Согласно бинарному поиску ключ KL должен сначала сравниться с ключом K[i] записи R[i], находящейся в середине таблицы (i=(ng+vg) div 2). Если KL >K[i], то отбрасывается (то есть больше не рассматривается) левая подтаблица - записи с меньшими ключами (ng=i+1) и поиск продолжается в правой подтаблице. Если KL<K[i], то отбрасывается правая подтаблица - записи с большими ключами (vg=i-1) и дальнейший поиск осуществляется в левой подтаблице.

Процесс деления подтаблиц пополам продолжается до тех пор, пока не возникнет одна из следующих ситуаций:

1) KL=K[i] - запись найдена;

2)KL<>K[i], ng>vg – ключи не совпали, а длина последней подтаблицы равна 1; это означает, что искомой записи в таблице нет.

Средняя длина дихотомического поиска равна log2n - 1. В худшем случае понадобится log2n + 1 сравнений. Это значительно лучше, чем при последовательном поиске.

В качестве примера рассмотрим поиск записи с ключом равным 30 (KL=30) в упорядоченной по возрастанию таблице (приведены ключи записей):



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

Замечание

На практике используется также следующая модификация метода: выбирается наибольшая степень двойки, не превосходящая длину таблицы, и на первом шаге обращаются к записи с номером, равным полученной степени. Если по результатам сравнения одна часть таблицы отбрасывается, то в оставшейся части также выбирается запись с номером, равным наибольшей степени двойки, и так далее.
^ Дихотомический поиск нескольких записей
Если в таблице может быть несколько записей с заданным значением ключа, то в процедуре поиска нужно определить индекс первой (i1) и индекс последней (i2) записей с этим ключом.

В качестве примера рассмотрим поиск записей с ключом равным ^ 33 (KL=33) в упорядоченной по возрастанию таблице (приводятся ключи записей).

Const Nmax=100;

Type

Rec=Record

kl : integer; {ключ записи}

inf :string[10];{информационное поле}

End;

Table = Array[1..Nmax] Of Rec;

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

procedure search(Var T: Table; n, key: integer; var k: integer);

{ T – таблица, n-число записей в таблице, key- значение ключа поиска}

{ k-номер найденной записи (k=0 при неуспешном поиске)}

var

ng ,vg, i: integer;

fl: boolean;

Begin

ng:=1; vg:= n;

fl:=false; k:=0;

while (ng<=vg) and not fl do

begin

i:=(ng+vg) div 2;

if keythen

vg:=i-1

else

if key>T[i].kl then

ng:=i+1

else

begin

fl:=true;

k:=i

end

end

end;
Рисунок 2 – Процедура дихотомического поиска записи
Пример поиска нескольких записей:



Процедура поиска в этом случае имеет вид:

^ Const Nmax=100;

Type

Rec=Record

kl : integer; {ключ записи}

inf :string[10];{информационное поле}

End;

Table = Array[1..Nmax] Of Rec;

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Рrocedure search-2 (Var T: Table; key, n: integer; var i1, i2: integer);

{ T – таблица, n-число записей в таблице, key- значение ключа поиска}

{ i1-номер первой найденной записи, i2-номер последней}

var

ng ,vg, i: integer;

fl: boolean;

Begin

ng:=1; vg:= n; fl:=false;

i1:=0; i2:=0;

while (ng<=vg) and not fl do

begin

i:=(ng+vg) div 2;

if keythen

vg:=i-1

else

if key>T[i].kl then

ng:=i+1

else

fl:=true;

end ;

if fl then

begin

i1:=i; i2:=i;

while (i1>1) and (T[i1-1].kl=key) do

i1:=i1-1;

while (i2and (T[i2+1].kl=key) do

i2:=i2+1;

end;

end;

Дихотомический поиск по близости

Задачей поиска по близости является определение одной или двух записей, ключи которых наиболее близки к значению ключа поиска (в частности, возможно точное совпадение ключей записи и поиска). Алгоритм такого поиска основывается на алгоритме поиска по совпадению.

В качестве примера рассмотрим следующую последовательность ключей (ключи записей упорядоченной таблицы):

индексы записей

1

2

3

4

5

6

7

8

9

10

ключи

5

8

12

15

18

20

21

25

28

30


^ Определить записи, наиболее близкие к задаваемому ключу KL:
1) KL=22

Результатом поиска: запись с ключом 21 (индекс равен 7).

2) KL=27

Результат поиска: запись с ключом 28 (индекс равен 9).

3) KL=19

Результат поиска: записи с ключами 18 и 20 (индексы равны 5, 6).
4) KL=12

Результат поиска: запись с индексом 3 (точное совпадение).

^ Используя поиск по близости, можно также найти записи, ключи которых больше (меньше) заданного. Например:

1) Определить записи, ключи которых >=22.

Результат поиска: записи с индексами от 8 до 10.

2) Определить записи, ключи которых <=15.

Результат поиска: записи с индексами от 1 до 4.

1   2   3   4   5   6   7   8   9   ...   19

Похожие:

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconФизика методические указания к лабораторным работам 10, 31
Козлов В. А., Курушин А. Д., Серов Е. А. Физика. Методические указания к лабораторным работам 10, 31 // Под общ ред доц. С. Г. Стоюхина....

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и задания к лабораторным работам по курсам “
Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 050102 “Программное обеспечение...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным наборам предназначены для студентов,...
Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Автоматизация...
Сапр простейшей структуры на основе расчета и анализа критериев эффективности с использованием имитационных моделей

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по курсу “
В прологе предусматриваются основные арифметические операции +, -, /, ×, mod, div. Чтобы заставить систему выполнить присваивание...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания к лабораторным работам по дисциплине «Программирование»
Тема: Разработка классов, создание конструкторов и деструкторов. Использование статических членов класса

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconУчебное пособие к лабораторным работам
Автоматизированные информационно-управляющие системы: учебное пособие к лабораторным работам / Л. С. Казаринов, Т. А. Барбасова,...

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconКонтрольные задания по курсу «Экономико-математическое моделирование»...
Контрольные задания по курсу «Экономико-математическое моделирование» и методические указания к их выполнению

Методические указания и задания к лабораторным работам по курсу \"алгоритмы и структуры данных \" iconМетодические указания и контрольные задания к выполнению контрольных...
В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница