24.03.2019, 00:55 [+3 UTC]
в нашей команде: 3 482 чел. | участники онлайн: 5 (рекорд: 21)

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

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

все разделы

правила

новости

участники

доска почёта

форум

блоги

поиск

статистика

наш журнал

наши встречи

наша галерея

отзывы о нас

поддержка

руководство

Версия системы:
7.73 (23.03.2019)
JS-v.1.33 | CSS-v.3.35

Общие новости:
09.03.2019, 10:08

Форум:
23.03.2019, 10:45

Последний вопрос:
23.03.2019, 23:41
Всего: 149069

Последний ответ:
23.03.2019, 18:46
Всего: 258019

Последняя рассылка:
23.03.2019, 20:45

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

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

Наша кнопка:

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

Отзывы о нас:
15.05.2012, 10:03 »
Иван Васильевич Митяев
спасибо! [вопрос № 186015, ответ № 270810]
29.11.2009, 09:56 »
R.A.M
Большое спасибо за ответ! Вчера посмотрел на другом компьютере, WINDOWS 7 приняла мою видеокарту как RV630, и в течении 10 минут ни одного намёка на глюки не было. [вопрос № 174610, ответ № 257032]

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

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

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

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

Коцюрбенко Алексей Владимирович
Статус: Модератор
Рейтинг: 732
Зенченко Константин Николаевич
Статус: Старший модератор
Рейтинг: 519
solowey
Статус: Студент
Рейтинг: 126

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

Консультация онлайн # 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
неизвестный

# 1

= общий = | 16.12.2006, 07:23

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

 

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

Яндекс Rambler's Top100

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

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

© 2001-2019, Портал RFPRO.RU, Россия
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.73 от 23.03.2019
Версия JS: 1.33 | Версия CSS: 3.35