Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.96
Bloomfield
2 / 2 / 1
Регистрация: 16.11.2009
Сообщений: 51
#1

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

24.06.2010, 15:30. Просмотров 3781. Ответов 7
Метки нет (Все метки)

Нужен код сортировки бинарными вставками, но работающего кода не нашёл.
Поэтому написать думаю можно так:
Взять сортировку вставками, и вставить в то место, где поиск места для вставки, бинарный поиск? или что то менять нужно в коде??
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2010, 15:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка вставками + бинарный поиск = (C++):

Сортировка вектора по полю(Сортировка вставками) - C++
Здравствуйте! Нужно написать сортировку вектора по полю weight класса tomato. Вот класс: #pragma once #include <iostream> ...

Сортировка Шелла и сортировка вставками - C++
Напишите программу для: 1)Сортировка вставкой 2)сортировка Шелла

Сортировка вставками - C++
Где-то ошибка в цикле... помогите) ... int array = {3, 2, 1}, min = 0, a = 0, b = 0; ... for(a = 1; a < size; ++a); ...

Сортировка вставками - C++
Программа работает, но криво( Нужно, что бы 10 массивов рандомных было, а не один. И еще плохо считает в рандомном массиве сравнения. ...

Сортировка вставками - C++
#include <stdio.h> #include <iostream> #include <ctime> using namespace std; const int n = 1000; int size; void...

Сортировка вставками - C++
Доброго времени суток, форумчане. Подскажите, пожалуйста, почему при первой реализации алгоритма массив упорядочивается, а при второй -...

7
AemClock
6 / 6 / 1
Регистрация: 04.06.2010
Сообщений: 19
24.06.2010, 15:56 #2
А смысл в сортировке вставками двоичный поиск ? Все равно после поиска вставку элемента придется делать линейно
0
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;
    }
а как можно улучшить его и получить метод бинарных вставок? нужно при поиске делить массив пополам?
0
AemClock
6 / 6 / 1
Регистрация: 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 / 1
Регистрация: 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 / 1
Регистрация: 04.06.2010
Сообщений: 19
25.06.2010, 13:27 #8
Ну а в чем тогда проблема ?
0
25.06.2010, 13:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.06.2010, 13:27
Привет! Вот еще темы с ответами:

Сортировка вставками - C++
Необходимо отсортировать весь массив методом вставками парных чисел на возрастание const int N = 4; int mas; void fill(){ ...

Сортировка вставками - C++
Помогите плиз немогу написать программу, незнаю с чего начать и что писать, может у кого что нить завалялось для этой темы, заранее спс ...

Сортировка вставками - C++
Условие: Дан массив целых чисел. Ваша задача — отсортировать его в порядке неубывания с помощью сортировки вставками. Сортировка...

Сортировка вставками - C++
Помогите написать программу на языке &quot;СИ&quot; Сортировка вставками. Дана последовательность чисел a1, a2, …, an . Требуется представить ...


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

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

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