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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.84
GetVariable
163 / 119 / 5
Регистрация: 17.03.2013
Сообщений: 283
#1

Алгоритм сортировки Шелла - C++

18.03.2013, 15:17. Просмотров 3397. Ответов 6
Метки нет (Все метки)

PHP
1
http://lord-n.narod.ru/download/books/walla/programming/Spr_po_C/21/2107.htm
здесь сказано, что существует, некая последовательность шагов 9 5 3 2 1.

как собственно, рассчитать сколько нужно шагов сделать для конкретного массива?

5 4 3 2 1

и

10 9 8 7 6 5 4 3 2 1
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.03.2013, 15:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм сортировки Шелла (C++):

Сравнение алгоритмов сортировки ... алгоритм Шелла - C++
Вопрос такой, для лабораторной работы нужно сравнить три алгоритма сортировки чисел ... так вот измеряю время работы : double start...

Составить блок – схемы для шейкер- сортировки и сортировки Шелла - C++
Доброго времени суток, очень нужна ваша помощь в решении данной проблемы, буду бесконечно благодарен. Составить блок – схемы для шейкер-...

Метод сортировки Шелла - C++
Написать программу которая реализует метод сортировки Шелла. Сгенерировать три массива 100, 1.000 и 10.000 элементов типа integer...

Метод сортировки Шелла - C++
помогите дописать программу в case 6 СТРОИТЕЛЬНАЯ КОМПАНИЯ (поля: заказчик, вид строительных работ, продолжительность работ,...

Переделка сортировки Шелла - C++
Товарищи и друзья! Только не закидывайте меня тухлыми яйцами и не понижайте карму!:) Я нашел такую вещь, что здесь на форуме неправильно...

Доработка сортировки методом Шелла - C++
Здравствуйте, форумчане! Помогите доработать программу, нужно, чтобы можно было сделать выбор, каким образом заполнить массив. У меня...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
xtorne21st
интересующийся
304 / 275 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
18.03.2013, 17:25 #2
Цитата Сообщение от GetVariable Посмотреть сообщение
как собственно, рассчитать сколько нужно шагов сделать для конкретного массива?
Эффективность алгоритма сортировки на общем основании рассчитать нельзя. Но для конкретного случая можно. На что затрачиваются ресурсы при вычислении? 1) Cравнение (затраты не значительны), 2) обмен элементов (затраты значительны). Для вашего случая, если хотите посчитать количество обменов то можете просто задать переменную, которая будет инкрементировать своё значение при каждом соответствии условию. О сложности данного алгоритма, а также о его эффективности в ссылке предъявленной вами это обсуждается.
0
Байт
Эксперт C
16062 / 10331 / 1540
Регистрация: 24.12.2010
Сообщений: 19,471
18.03.2013, 17:29 #3
Цитата Сообщение от xtorne21st Посмотреть сообщение
1) Cравнение (затраты не значительны), 2) обмен элементов (затраты значительны).
Тоже, знаете ли, от конкретной задачи зависит. Если к примеру имеем сто-байтовые ключи, а переставляем не сами записи, а только их 4-х байтовые указатели...
1
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
18.03.2013, 19:11 #4
Цитата Сообщение от GetVariable Посмотреть сообщение
http://lord-n.narod.ru/download/books/walla/programming/Spr_po_C/21/2107.htm
Странная книга, ничего не указано о том, как выбираются последовательности шагов для сортировки.

Щас исправим. Существует довольно много убывающих последовательностей шагов, при которых эффективность сортировки довольно высока.
Например, последовательность, предложенная Кнутом, такого вида: ... 121 40 13 4 1, или в виде формулы: h(i) = 3*i + 1. Начинать нужно с максимального h, меньшего чем размер сортируемого массива, а для вычисления следующего шага просто делить h на 3 без остатка.
Еще существует много последовательностей, основанных на формулах
Также используются убывающие последовательности, которые не расчитываются по формулам, а выбираются эмпирически или на основе хиртых правил
Можно использовать убывающую последовательность вида ...32 16 8 4 2 1, начиная с наибольшей степени числа 2, меньшей размера массива. но эта последовательность очень плохая.

В Седжвике довольно подробно описано про сортировку Шелла. Скачайте книгу и не поленитесь прочитать соответствующий раздел

Добавлено через 9 минут
Слегка накосячил с Кнутом, правильная последовательность расчитывается по формуле hi = 3*hi-1 + 1
2
GetVariable
163 / 119 / 5
Регистрация: 17.03.2013
Сообщений: 283
18.03.2013, 19:43  [ТС] #5
Цитата Сообщение от ya_noob Посмотреть сообщение
Странная книга, ничего не указано о том, как выбираются последовательности шагов для сортировки.

Щас исправим. Существует довольно много убывающих последовательностей шагов, при которых эффективность сортировки довольно высока.
Например, последовательность, предложенная Кнутом, такого вида: ... 121 40 13 4 1, или в виде формулы: h(i) = 3*i + 1. Начинать нужно с максимального h, меньшего чем размер сортируемого массива, а для вычисления следующего шага просто делить h на 3 без остатка.
Еще существует много последовательностей, основанных на формулах
Также используются убывающие последовательности, которые не расчитываются по формулам, а выбираются эмпирически или на основе хиртых правил
Можно использовать убывающую последовательность вида ...32 16 8 4 2 1, начиная с наибольшей степени числа 2, меньшей размера массива. но эта последовательность очень плохая.

В Седжвике довольно подробно описано про сортировку Шелла. Скачайте книгу и не поленитесь прочитать соответствующий раздел

Добавлено через 9 минут
Слегка накосячил с Кнутом, правильная последовательность расчитывается по формуле hi = 3*hi-1 + 1
ок ок. а как тогда с этой формулой произвести расчёт массива 5 4 3 2 1?
0
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
18.03.2013, 19:57 #6
Цитата Сообщение от GetVariable Посмотреть сообщение
а как тогда с этой формулой произвести расчёт массива 5 4 3 2 1?
какой расчет? отсортировать? я же написал (для Кнута): выбираем для шага максимальное значение последовательности (в нашем случае 4) и сортируем. далее делим 4 на 3 без остатка и получаем 1, следовательно снова сортируем теперь с шагом 1 и... всё. последовательность отсортирована.

Добавлено через 6 минут
а понял, вы имеете ввиду расчитать количество шагов. Элементарно же. на основе вышеописанного для последовательности 5 4 3 2 1 надо сделать 2 шага.
а в общем случае берем максимальное значение шага, уменьшаем по правилу до тех пор, пока шаг не станет равным 1 и считаем сколько раз уменьшали. значение счетчика и будет искомой величиной
1
GetVariable
163 / 119 / 5
Регистрация: 17.03.2013
Сообщений: 283
18.03.2013, 20:32  [ТС] #7
Цитата Сообщение от ya_noob Посмотреть сообщение
какой расчет? отсортировать? я же написал (для Кнута): выбираем для шага максимальное значение последовательности (в нашем случае 4) и сортируем. далее делим 4 на 3 без остатка и получаем 1, следовательно снова сортируем теперь с шагом 1 и... всё. последовательность отсортирована.

Добавлено через 6 минут
а понял, вы имеете ввиду расчитать количество шагов. Элементарно же. на основе вышеописанного для последовательности 5 4 3 2 1 надо сделать 2 шага.
а в общем случае берем максимальное значение шага, уменьшаем по правилу до тех пор, пока шаг не станет равным 1 и считаем сколько раз уменьшали. значение счетчика и будет искомой величиной
Действие алгоритма:

1. Сначала сортируются все элементы, отстоящие друг от друга на 4 позиции" 5 = (4 * 3 - 1) / 3 = 4
2. Затем сортируются элементы, расположенные на расстоянии 1 позиции. 4 / 3 = 1
3. Наконец, сортируются все соседние элементы.

вот так?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.03.2013, 20:32
Привет! Вот еще темы с ответами:

Ребят доработайте код программы (программа сортировки чисел методом Шелла) - C++
Нужна помощь Есть программа сортировки чисел методом шелла ее надо дописать чтоб она спрашивала 1 - введите сами 2 – рандом Если...

Алгоритм Шелла - C++
Приветствую, CyberForum. Пересмотрел много видео про Алгоритм Шелла, где плясали и роботы показывали наглядно как всё это делается, но...

алгоритм Шелла - C++
как увеличить скорость этого алгоритма Шелла в 2 раза .... Где-то читал про Сортировку методом Шелла-Кнута. Кнут просто подобрал...

Написать программу для сортировки массива способами шелла вставки слияния и пузырьком - C++
Написать программу для сортировки массива способами шелла вставки слияния и пузырьком в одной программе со всеми операторами и объяснением...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
18.03.2013, 20:32
Ответ Создать тему
Опции темы

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