Geum.ru

Варианты заданий 37 Контрольные вопросы к защите ргр: 39

Вид материалаКонтрольные вопросы

Содержание


Сортировка бинарными вставками
Сортировка Шелла
Подобный материал:
1   2   3   4   5   6   7   8

Сортировка бинарными вставками


Сортировку простыми вставками можно модифицировать, если при поиске «подходящего места» для вставляемого элемента использовать метод двоичного поиска. Среди отсортированной части массива выберем серединный1 элемент и сравним его с ключом. Если ключ меньше этого элемента, то поиск места вставки следует продолжать в левой половине упорядоченной части массива, иначе – в правой половине. Эта схема получила название сортировки бинарными вставками. Она была предложена Жд. Мочли в 1946 г. и была одной из первых публикаций по методам компьютерной сортировки.

Сортировка Шелла


Сортировка Шелла также является модификацией сортировки вставками. Метод данной сортировки основан на группировке элементов массива на несколько групп, например, на 8 групп по 2 записи. При этом элементы каждой группы отстоят друг от друга «расстоянии» h. Элементы каждой группы упорядочиваются методом простой вставки. Далее элементы массива снова группируются: на 4 группы по 4 элемента. Далее группировка выполняется на 8 групп по 2 элемента, и процесс завершается сортировкой всех элементов массива. При такой группировке упорядоченность элементов осуществляется большими скачками, что значительно сокращает количество перестановок.

Пример 4

Пример сортировки по неубыванию массива чисел

М ={12,6,65,7,0,4,9,16,36,7,64,13,25,1,44,5} методом Шелла.


1 проход. Сгруппируем массив чисел на 8 групп по 2 элемента, шаг смещения h=8: {M[1] и M[9]}, {M[2] и M[10]}, {M[3] и M[11]}, {M[4] и M[12]}, {M[5] и M[13]}, {M[6] и M[14]}, {M[7] и M[15]}, {M[8] и M[16]}.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




12
6
65
7
0
4
9
16
36
7
64
13
25
1
44
5



Применим к этим группам метод сортировки вставками.

1-я
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

группа
12





















36
























2-я
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

группа



6





















7





















3-я
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

группа






64





















65


















4-я
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

группа









7





















13















5-я
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

группа












0





















25












6-я
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

группа















1





















4









7-я
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

группа


















9





















44






8-я
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

группа





















5





















16


В итоге получим следующий массив:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




12
6
64
7
0
1
9
5
36
7
65
13
25
4
44
16


2 проход. Сгруппируем массив на 4 группы по 4 элемента, h=4: {M[1], M[5], M[9], M[13]}, {M[2], M[6], M[10], M[14]}, { M[3], M[7], M[11], M[15]}, { M[4], M[8], M[12], M[16]}.

Рассмотрим упорядочивание 1-ой группы элементов методом простых вставок:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

12
6
64
7
0
1
9
5
36
7
65
13
25
4
44
16




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

0









12









36









25









1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

0









12









25









36









В результате упорядочивания аналогичным способом элементов остальных групп имеем следующий массив:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

0
6
64
7
12
1
9
5
25
7
65
13
36
4
44
16


3 проход. Шаг смещения снова сокращаем в два раза и сортируем 2 группы по 8 элементов: { M[1], M[3], M[5], M[7], M[9], M[11], M[13], M[15]}, {M[2], M[4], M[6], M[8], M[10], M[12], M[14], M[16]}.

Элементы 1-ой группы отстоят друг от друга на расстоянии h=2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

0
6
64
7
12
1
9
5
25
7
65
13
36
4
44
16




Упорядочивание вставками каждой группы:

1-я
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

группа
0



9



12



25



36



44



64



65






2-я
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

группа



1




4




5



6



7




7




13



16


В итоге имеем частично отсортированный массив:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




0
1
9
4
12
5
25
6
36
7
44
7
64
13
65
16


4 проход. Последний проход, h=1, сортируется полностью весь массив.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




0
1
9
4
12
5
25
6
36
7
44
7
64
13
65
16






1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




0
1
4
5
6
7
7
9
12
13
16
25
36
44
64
65


Метод сортировки Шелла также известен под названием сортировки с убывающим смещением, поскольку каждая группировка характеризуется смещением h, то есть элементы одной группы отстоят друг от друга на шаг смещения h. Последовательность смещений 8,4,2,1 не следует считать незыблемой, можно пользоваться любой последовательностью hi-1, hi-2, …h0, но последнее смещение h0 должно быть равно 1. Например, этот же массив чисел с таким же успехом можно было отсортировать с помощью последовательности смещений: 6,3,2,1.


H=6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




12
6
65
7
0
4
9
16
36
7
64
13
25
1
44
5







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




9
1
36
5
0
4
12
6
44
7
64
13
25
16
65
7




H=3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




9
1
36
5
0
4
12
6
44
7
64
13
25
16
65
7







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




5
0
4
7
1
13
7
6
36
9
16
44
12
64
65
25




H=2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




5
0
4
7
1
13
7
6
36
9
16
44
12
64
65
25







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




1
0
4
6
5
7
7
9
12
13
16
25
36
44
65
64




H=1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




1
0
4
6
5
7
7
9
12
13
16
25
36
44
65
64







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16




0
1
4
5
6
7
7
9
12
13
16
25
36
44
64
65