19.09.2018, 16:54 [+3 UTC]
в нашей команде: 2 970 чел. | участники онлайн: 5 (рекорд: 21)

:: РЕГИСТРАЦИЯ

:: задать вопрос

:: все разделы

:: правила

:: новости

:: участники

:: доска почёта

:: форум

:: блоги

:: поиск

:: статистика

:: наш журнал

:: наши встречи

:: наша галерея

:: отзывы о нас

:: поддержка

:: руководство

Версия системы:
7.50 (13.09.2018)

Общие новости:
13.04.2018, 10:33

Форум:
18.09.2018, 08:51

Последний вопрос:
19.09.2018, 12:40

Последний ответ:
19.09.2018, 08:03

Последняя рассылка:
18.09.2018, 17:15

Писем в очереди:
3

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
10.06.2011, 17:23 »
TAIDA
Благодарю! Уже кое что проясняется! [вопрос № 183575, ответ № 267672]
30.05.2017, 17:01 »
Tati77
Спасибо Андрею Владимировичу за быстрый и правильный ответ! [вопрос № 191070, ответ № 275046]
06.03.2017, 19:08 »
crater.10
Спасибо, будем разбираться с этой таблицей. [вопрос № 190608, ответ № 274695]

РАЗДЕЛ • С / С++

Создание программ на языках C и C++.

[администратор рассылки: Андрей Кузнецов aka Dr_Andrew (Старший модератор)]

Лучшие эксперты в этом разделе

Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 93
solowey
Статус: Студент
Рейтинг: 19
CradleA
Статус: Профессор
Рейтинг: 1

Перейти к консультации №:
 

Консультация онлайн # 67163
Раздел: • С / С++
Автор вопроса: Андрюхаха
Отправлена: 15.12.2006, 20:57
Поступило ответов: 1

объясните пожалуйста способ сортировки бинарными вставками.

вот требуемая программа:
Упорядочить массив, используя алгоритм сортировки бинарными вставками, в котором место размещения элемента в упорядоченном массиве определяется методом бинарного поиска.

Состояние: Консультация закрыта

Ответ # 131872 от Олег Владимирович

Здравствуйте, Андрюхаха!

Алгоритм сортировки вставкой подразумевает виртуальное разделение массива на две части - слева отсортированную и справа ещё неотсортированную. Каждый первый элемент правого подмассива вставляется в левый так, чтобы его отсортированность не нарушилась. То есть алгоритм вставки действует, например, так:
массив 4 7 1 10 3
подразумеваем, что самое начало отсортировано
4 | 7 1 10 3
вставляем 7 после 4
4 7 | 1 10 3
1 надо вставить перед 4
1 4 7 | 10 3
10 - после 7
1 4 7 10 | 3
3 - между 1 и 3
1 3 4 7 10|. Всё
Таким образом, задача сортировки сведена к поиску номера элемента массива, который меньше заданного числа, но следующий за ним элемент уже больше заданного числа. Применяется метод бинарного поиска. Этот метод применим только к отсортированному массиву.
Принцип следующий. Рассматривается сначала целый массив, допустим, [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.
Реализация в приложении. Процедура sort принимает два параметра - сортируемый массив и его размер. Ничего не возвращает, просто модифицирует заданный массив.
Удачи!

Приложение:


Консультировал: Олег Владимирович
Дата отправки: 15.12.2006, 22:35

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Мини-форум консультации № 67163

Посетитель

ID: 28013

# 1

= общий = | 16.12.2006, 07:23 | цитировать цитировать  | профиль профиль  |  отправить письмо в личную почту пейджер

спасибо огромное!

 

Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.36326 сек.

© 2001-2018, Портал RFPRO.RU, Россия
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.50 от 13.09.2018