Программирование на языке Pascal




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


Сортировку простыми вставками можно немного улучшить: поиск "подходящего места" в упорядоченной последовательности можно вести более экономичным способом, который называется Двоичный поиск в упорядоченной последовательности. Он напоминает детскую игру "больше-меньше": после каждого сравнения обрабатываемая последовательность сокращается в два раза.

Пусть, к примеру, нужно найти место для элемента 7 в таком массиве:

[2 4 6 8 10 12 14 16 18]

Найдем средний элемент этой последовательности (10) и сравним с ним семерку. После этого все, что больше 10 (да и саму десятку тоже), можно смело исключить из дальнейшего рассмотрения:

[2 4 6 8] 10 12 14 16 18

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

nomer_sred:= (nomer_lev + nomer_prav)div 2

Итак, отсечем половину последовательности:

2 4 [6 8] 10 12 14 16 18

И снова:

2 4 6 [8] 10 12 14 16 18 2 4 6][8 10 12 14 16 18

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

[2 4 6 8] 10 12 14 16 18 2 4 [6 8] 10 12 14 16 18 2 4 6 [8] 10 12 14 16 18 2 4 6 8][10 12 14 16 18

Из приведенных примеров уже видно, что поиск ведется до тех пор, пока левая граница не окажется правее(!) правой границы. Кроме того, по завершении этого поиска последней левой границей окажется как раз тот элемент, на котором необходимо закончить сдвиг "хвоста" последовательности.

Будет ли такой алгоритм универсальным? Давайте проверим, что же произойдет, если мы станем искать позицию не для семерки или девятки, а для единицы:

[2 4 6 8] 10 12 14 16 18 [2] 4 6 8 10 12 14 16 18 ][2 4 6 8 10 12 14 16 18




Содержание  Назад  Вперед