Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/2: Рейтинг темы: голосов - 2, средняя оценка - 5.00
SrgKord
47 / 29 / 2
Регистрация: 14.02.2013
Сообщений: 655
1

Как происходит сортировка бинарными вставками?

21.02.2014, 13:37. Просмотров 433. Ответов 1
Метки нет (Все метки)

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

Пусть, к примеру, нужно найти место для элемента 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). Таким образом, если левая граница вышла за рассматриваемый диапазон, получается, что ничего сдвигать не нужно. Вообще же такие действия выглядят явно лишними, поэтому от них стоит застраховаться, введя одну дополнительную проверку в текст алгоритма.


Но эта статья объясняет только, как вставлять ключи в готовый массив, но как сортировать перемешанный массив из статьи не ясно. И вообще, именно по бинарным вставкам в сети информации я не нашел.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.02.2014, 13:37
Ответы с готовыми решениями:

Сортировка вставками
Здравствуйте! Скажите, пожалуйста, основное преимущество простых вставок над бинарными. Очень...

Сортировка бинарными вставками
Имеется функция сортировки бинарными вставками, нужна программа, в которой она будет...

Сортировка бинарными вставками
Сортировка бинарными вставками работает неправильно. Помогите найти ошибку. Вот код: template...

Сортировка бинарными вставками
Кому не трудно, объясните на пальцах. Вот допустим дан одномерный массив 4 6 2 9 12 16. Нужно...

Сортировка бинарными вставками
Привет! Есть код к сортировке бинарными вставками (сортируется одномерный массив), но он не...

1
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 953
22.02.2014, 10:31 2
Но эта статья объясняет только, как вставлять ключи в готовый массив, но как сортировать перемешанный массив из статьи не ясно. И вообще, именно по бинарным вставкам в сети информации я не нашел.
А основная идея в том чтобы использовать метод сортировки вставками, но вместо кода для вставки проводить бинарный поиск места куда вставить, а потом уже без ненужных теперь проверок "раздвинуть" отсортированную часть массива и вставить новый элемент куда надо.

Странно, я сейчас рядом с точной копией такого описания нашел код
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  for  i:= 2  to  n  do   
      if  a[i-1]>a[i]  then 
      begin
         x:= a[i];  
         left:= 1;  
         right:= i-1;  
         repeat    
            sred:= (left+right) div 2;    
            if  a[sred]<x  then  
               left:= sred+1  
               else  right:= sred-1;      
         until  left>right;
         for j:=i-1 downto left  do
            a[j+1]:= a[j];  
         a[left]:= x;
       end;
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.02.2014, 10:31

Сортировка бинарными вставками
Если у кого нибудь есть, выложите рабочий код сортировки бинарными вставками. Просто Си.Буду...

Сортировка бинарными вставками
Здравствуйте, возникла проблема с сортировкой бинарными вставками. Сортировка по возрастанию....

Сортировка бинарными вставками.
Никак не могу написать программу для этого алгоритма. Или я что-то не так понимаю или реализую не...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru