Сортировка вставками + бинарный поиск =

@Bloomfield · Регистрация: 16.11.2009

Author24 — интернет-сервис помощи студентам

Нужен код сортировки бинарными вставками, но работающего кода не нашёл.
Поэтому написать думаю можно так:
Взять сортировку вставками, и вставить в то место, где поиск места для вставки, бинарный поиск? или что то менять нужно в коде??

@AemClock · 24.06.2010, 15:56

А смысл в сортировке вставками двоичный поиск ? Все равно после поиска вставку элемента придется делать линейно

@Bloomfield · 24.06.2010, 18:18 **[ТС]**

с помощью бинарного поиска нашёл место куда вставлять элемент и вставил... не?

Добавлено через 1 час 35 минут
Вот сортировка вставками

C

int i, j, temp;
    for (i = 1; i < size; i++) {
        temp = A[i];
        for (j = i - 1; j >= 0; j--) {
            if (A[j] < temp) {
                break;
            }
            A[j+1] = A[j];
        }
        A[j+1] = temp;
    }

а как можно улучшить его и получить метод бинарных вставок? нужно при поиске делить массив пополам?

@AemClock · 24.06.2010, 20:27

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

@Bloomfield · 24.06.2010, 21:24 **[ТС]**

А как тогда замутить сортировку бинарными вставками?

@AemClock · 24.06.2010, 22:19

В первый раз про такое слышу О_о Хотя не совсем понятно что имеется ввиду по бинарными вставками, искать элемент можно, а вставлять не получается

@Bloomfield · 25.06.2010, 05:25 **[ТС]**

Например:
Рассматривается сначала целый массив, допустим, [1 4 7 10] (вставка тройки). Он разбивается на две половинки, и граничный элемент сравнивается с заданным числом; если число превосходит границу, оно должно быть вставлено в правую половинку - так что рассматриваем её, иначе берём левую половинку. 3<4 => [1 4] 7 10. Далее повторяем алгоритм - половинизируем рассматриваемую часть и выбираем место, куда вставить требуемое число. 3>1 => 1 [4] 7 10 ; 3<4 => 1 [] 4 7 10. Вставляем - 1 [3] 4 7 10.

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

@AemClock · 25.06.2010, 13:27

Ну а в чем тогда проблема ?

@Bloomfield 2 / 2 / 1 Регистрация: 16.11.2009 Сообщений: 51
		1
	Сортировка вставками + бинарный поиск = 24.06.2010, 15:30. Показов 10501. Ответов 7 Метки нет (Все метки) Нужен код сортировки бинарными вставками, но работающего кода не нашёл. Поэтому написать думаю можно так: Взять сортировку вставками, и вставить в то место, где поиск места для вставки, бинарный поиск? или что то менять нужно в коде?? 0

@AemClock 6 / 6 / 0 Регистрация: 04.06.2010 Сообщений: 19
	24.06.2010, 15:56	2
	А смысл в сортировке вставками двоичный поиск ? Все равно после поиска вставку элемента придется делать линейно 0

@AemClock 6 / 6 / 0 Регистрация: 04.06.2010 Сообщений: 19
	24.06.2010, 20:27	4
	Нет, кончено для поиска места вставки элемента можно использовать двоичный поиск, но после того как будет найдено место вставки, необходимо будет проделать это самое "вставил", а тут уже не обойтись без того же самого цикла, поэтому не вижу смысла использовать двоичный поиск. 0

@Bloomfield 2 / 2 / 1 Регистрация: 16.11.2009 Сообщений: 51
	24.06.2010, 21:24 [ТС]	5
	А как тогда замутить сортировку бинарными вставками? 0

@AemClock 6 / 6 / 0 Регистрация: 04.06.2010 Сообщений: 19
	24.06.2010, 22:19	6
	В первый раз про такое слышу О_о Хотя не совсем понятно что имеется ввиду по бинарными вставками, искать элемент можно, а вставлять не получается 0

@Bloomfield 2 / 2 / 1 Регистрация: 16.11.2009 Сообщений: 51
	25.06.2010, 05:25 [ТС]	7
	Например: Рассматривается сначала целый массив, допустим, [1 4 7 10] (вставка тройки). Он разбивается на две половинки, и граничный элемент сравнивается с заданным числом; если число превосходит границу, оно должно быть вставлено в правую половинку - так что рассматриваем её, иначе берём левую половинку. 3<4 => [1 4] 7 10. Далее повторяем алгоритм - половинизируем рассматриваемую часть и выбираем место, куда вставить требуемое число. 3>1 => 1 [4] 7 10 ; 3<4 => 1 [] 4 7 10. Вставляем - 1 [3] 4 7 10. Получается сортировка бинарными вставками 0

@AemClock 6 / 6 / 0 Регистрация: 04.06.2010 Сообщений: 19
	25.06.2010, 13:27	8
	Ну а в чем тогда проблема ? 0