Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Читайте также:
  1. Обменная сортировка
  2. Сортировка
  3. Сортировка данных
  4. Сортировка данных
  5. Сортировка и поиск информации
  6. Сортировка результатов запроса
  7. Сортировка с помощью дерева (Heapsort)
  8. Сортировка Шелла
  9. Сортировка.

Пример сортировки

Эффективность алгоритма ПрВстБар

 

Понятно, что для этой сортировки наилучшим будет случай, когда на вход подается уже упорядоченная последовательность данных. Тогда алгоритм ПрВстБар совершит N-1 сравнение и 0 пересылок данных.

 

В худшем же случае - когда входная последовательность упорядочена "наоборот" - сравнений будет уже (N+1)*N/2, а пересылок (N-1)*(N+3). Таким образом, этот алгоритм имеет сложность ~N2 (читается "порядка эн квадрат") по обоим параметрам.

 

 

Предположим, что нужно отсортировать следующий набор чисел:

5 3 4 3 6 2 1

 

Выполняя алгоритм ПрВстБар, мы получим такие результаты (подчеркнута уже отсортированная часть массива, полужирным выделена сдвигаемая последовательность, а квадратиком выделен вставляемый элемент):

Состояние массива Сдвиги Сравнения Пересылки данных

0 шаг: 5343621

1 шаг: 5343621 1 1+ 13 1+ 24)

2 шаг: 3543621 1 1+1 1+2

3 шаг: 3453621 2 2+1 2+2

4 шаг: 3345621 0 1 0

5 шаг: 3345621 5 5+1 5+2

6 шаг: 2334561 6 6+1 6+2

Результат: 1233456 15 20 25

 

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

 

Пусть, к примеру, нужно найти место для элемента 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

 

Как видим, правая граница становится неопределенной - выходит за пределы массива. Будет ли этот факт иметь какие-либо неприятные последствия? Очевидно, нет, поскольку нас интересует не правая, а левая граница.

 

"А что будет, если мы захотим добавить 21?" - спросит особо въедливый читатель. Проверим это:

 

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][

 

Кажется, будто все плохо: левая граница вышла за пределы массива; непонятно, что нужно сдвигать...

 

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

 

<== предыдущая лекция | следующая лекция ==>
| Сортировка бинарными вставками

Дата добавления: 2013-12-13; Просмотров: 86; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ip: 54.221.93.187
Генерация страницы за: 0.021 сек.