Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.96
Bloomfield
2 / 2 / 1
Регистрация: 16.11.2009
Сообщений: 51
24.06.2010, 15:30     Сортировка вставками + бинарный поиск = #1
Нужен код сортировки бинарными вставками, но работающего кода не нашёл.
Поэтому написать думаю можно так:
Взять сортировку вставками, и вставить в то место, где поиск места для вставки, бинарный поиск? или что то менять нужно в коде??
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2010, 15:30     Сортировка вставками + бинарный поиск =
Посмотрите здесь:

Сортировка вставками C++
Сортировка вставками C++
C++ Сортировка вставками
Сортировка вставками C++
Сортировка вставками. C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AemClock
6 / 6 / 1
Регистрация: 04.06.2010
Сообщений: 19
24.06.2010, 15:56     Сортировка вставками + бинарный поиск = #2
А смысл в сортировке вставками двоичный поиск ? Все равно после поиска вставку элемента придется делать линейно
Bloomfield
2 / 2 / 1
Регистрация: 16.11.2009
Сообщений: 51
24.06.2010, 18:18  [ТС]     Сортировка вставками + бинарный поиск = #3
с помощью бинарного поиска нашёл место куда вставлять элемент и вставил... не?

Добавлено через 1 час 35 минут
Вот сортировка вставками
C
1
2
3
4
5
6
7
8
9
10
11
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
6 / 6 / 1
Регистрация: 04.06.2010
Сообщений: 19
24.06.2010, 20:27     Сортировка вставками + бинарный поиск = #4
Нет, кончено для поиска места вставки элемента можно использовать двоичный поиск, но после того как будет найдено место вставки, необходимо будет проделать это самое "вставил", а тут уже не обойтись без того же самого цикла, поэтому не вижу смысла использовать двоичный поиск.
Bloomfield
2 / 2 / 1
Регистрация: 16.11.2009
Сообщений: 51
24.06.2010, 21:24  [ТС]     Сортировка вставками + бинарный поиск = #5
А как тогда замутить сортировку бинарными вставками?
AemClock
6 / 6 / 1
Регистрация: 04.06.2010
Сообщений: 19
24.06.2010, 22:19     Сортировка вставками + бинарный поиск = #6
В первый раз про такое слышу О_о Хотя не совсем понятно что имеется ввиду по бинарными вставками, искать элемент можно, а вставлять не получается
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.

Получается сортировка бинарными вставками
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.06.2010, 13:27     Сортировка вставками + бинарный поиск =
Еще ссылки по теме:

C++ сортировка вставками
C++ Сортировка вставками
Сортировка вставками C++

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

Или воспользуйтесь поиском по форуму:
AemClock
6 / 6 / 1
Регистрация: 04.06.2010
Сообщений: 19
25.06.2010, 13:27     Сортировка вставками + бинарный поиск = #8
Ну а в чем тогда проблема ?
Yandex
Объявления
25.06.2010, 13:27     Сортировка вставками + бинарный поиск =
Ответ Создать тему
Опции темы

Текущее время: 11:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru