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

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

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

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

18.03.2013, 15:17. Просмотров 3364. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.03.2013, 15:17     Алгоритм сортировки Шелла
Посмотрите здесь:

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

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

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
xtorne21st
интересующийся
303 / 274 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
18.03.2013, 17:25     Алгоритм сортировки Шелла #2
Цитата Сообщение от GetVariable Посмотреть сообщение
как собственно, рассчитать сколько нужно шагов сделать для конкретного массива?
Эффективность алгоритма сортировки на общем основании рассчитать нельзя. Но для конкретного случая можно. На что затрачиваются ресурсы при вычислении? 1) Cравнение (затраты не значительны), 2) обмен элементов (затраты значительны). Для вашего случая, если хотите посчитать количество обменов то можете просто задать переменную, которая будет инкрементировать своё значение при каждом соответствии условию. О сложности данного алгоритма, а также о его эффективности в ссылке предъявленной вами это обсуждается.
Байт
Эксперт C
15835 / 10162 / 1522
Регистрация: 24.12.2010
Сообщений: 19,159
18.03.2013, 17:29     Алгоритм сортировки Шелла #3
Цитата Сообщение от xtorne21st Посмотреть сообщение
1) Cравнение (затраты не значительны), 2) обмен элементов (затраты значительны).
Тоже, знаете ли, от конкретной задачи зависит. Если к примеру имеем сто-байтовые ключи, а переставляем не сами записи, а только их 4-х байтовые указатели...
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
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
_
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 и считаем сколько раз уменьшали. значение счетчика и будет искомой величиной
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.03.2013, 20:32     Алгоритм сортировки Шелла
Еще ссылки по теме:

Реализовать алгоритм Шелла - C++
Очень прошу сильно помочь с сим заданием, сам я не могу, а очень надо ( Задача: Имеется массив действительных чисел. Необходимо...

Метод Шелла, алгоритм обмена - C++
Помогите написать программы. 1. Упорядочить заданный список целых значений методом Шелла. 2. Доно массив записей,каждый из которых...

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

Алгоритм сортировки - C++
Здравствуйте, подскажите пожалуйста какой алгоритм можно использовать при решении такой задачи: Дана строка char * из букв и цифр...

Алгоритм сортировки - C++
пацаны ребята помогите, реализовал два алгоритма на C++, алгоритм сортировки пирамидальный(кучей) и быстрой сортировки, все они сортируют...


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

Или воспользуйтесь поиском по форуму:
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     Алгоритм сортировки Шелла
Ответ Создать тему
Опции темы

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