10.12.2018, 10:43 [+3 UTC]
в нашей команде: 3 202 чел. | участники онлайн: 9 (рекорд: 19)

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

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

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

:: правила

:: новости

:: участники

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

:: форум

:: блоги

:: поиск

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

:: наш журнал

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

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

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

:: поддержка

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

Версия системы:
7.56 (09.12.2018)

Общие новости:
01.12.2018, 22:30

Форум:
08.12.2018, 14:26

Последний вопрос:
09.12.2018, 18:57

Последний ответ:
10.12.2018, 10:19

Последняя рассылка:
10.12.2018, 03:45

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

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

Наша кнопка:

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

Отзывы о нас:
09.10.2010, 17:19 »
scoop
Большое спасибо Вам за подробные объяснения и практические рекомендации, обязательно им последую. Уже сам не раз задумывался о ревизии и профилактике "железа". Очень Вам благодарен за ссылки на программу и учебный материал. [вопрос № 180188, ответ № 263401]
29.11.2009, 13:15 »
D1ver
Премного благодарен за исправления и за ответы на вопросы! [вопрос № 174604, ответ № 257054]
28.02.2012, 00:24 »
Reostat
Спасибо, сравниваю с ответом от Сергей Мороз. Из прочитанного ранее, строго как дилетант, заимел мнение, что Sandy Bridge более перспективный выбор. [вопрос № 185519, ответ № 270098]

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

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

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

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

Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 155
solowey
Статус: Студент
Рейтинг: 126
Андрей Кузнецов aka Dr_Andrew
Статус: Старший модератор
Рейтинг: 73

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

Консультация онлайн # 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.13713 сек.

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