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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.84
GetVariable
 Аватар для GetVariable
163 / 119 / 5
Регистрация: 17.03.2013
Сообщений: 283
18.03.2013, 15:17     Алгоритм сортировки Шелла #1
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
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
xtorne21st
интересующийся
300 / 271 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
18.03.2013, 17:25     Алгоритм сортировки Шелла #2
Цитата Сообщение от GetVariable Посмотреть сообщение
как собственно, рассчитать сколько нужно шагов сделать для конкретного массива?
Эффективность алгоритма сортировки на общем основании рассчитать нельзя. Но для конкретного случая можно. На что затрачиваются ресурсы при вычислении? 1) Cравнение (затраты не значительны), 2) обмен элементов (затраты значительны). Для вашего случая, если хотите посчитать количество обменов то можете просто задать переменную, которая будет инкрементировать своё значение при каждом соответствии условию. О сложности данного алгоритма, а также о его эффективности в ссылке предъявленной вами это обсуждается.
Байт
 Аватар для Байт
13993 / 8824 / 1231
Регистрация: 24.12.2010
Сообщений: 15,990
18.03.2013, 17:29     Алгоритм сортировки Шелла #3
Цитата Сообщение от xtorne21st Посмотреть сообщение
1) Cравнение (затраты не значительны), 2) обмен элементов (затраты значительны).
Тоже, знаете ли, от конкретной задачи зависит. Если к примеру имеем сто-байтовые ключи, а переставляем не сами записи, а только их 4-х байтовые указатели...
ya_noob
_
200 / 144 / 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
GetVariable
 Аватар для 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?
ya_noob
_
200 / 144 / 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 и считаем сколько раз уменьшали. значение счетчика и будет искомой величиной
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.03.2013, 20:32     Алгоритм сортировки Шелла
Еще ссылки по теме:

Алгоритм Шелла C++
C++ Составить блок – схемы для шейкер- сортировки и сортировки Шелла
C++ метод сортировки Шелла

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

Или воспользуйтесь поиском по форуму:
GetVariable
 Аватар для 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. Наконец, сортируются все соседние элементы.

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

Текущее время: 04:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru