CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Рисование множества Мандельброта. (38357 hits)
#Как работать с zip архивами стандартными средствами windows. (36500 hits)
#Летающие, крутящиеся шарики. (38248 hits)
#Подмножество с максимальной суммой. (119186 hits)
#Валидация, динамическая проверка заполнения html форм. (200565 hits)
#Заполнение 2-го выпадающего списка (select) в соответствии с выбором в первом. (40654 hits)
#Динамическое изменение цвета полоски прокрутки в IE5.5 и выше. (26485 hits)
#Пирамидальная сортировка. (188565 hits)
#Овал, вписанный в прямоугольник. (32065 hits)
#Вычисление эксцесса и коэффициентов асимметрии заданной выборки. (40446 hits)
#Вездесущий двоичный поиск.... (155883 hits)
#Программное создание ссылок. (94481 hits)
#Синус. (54185 hits)
#Сравнение алгоритмов сортировки массива. (166521 hits)
#Рисование 3D объекта. (29938 hits)
#Улучшение быстрой сортировки. (67905 hits)
#Подсветка синтаксиса. (26998 hits)
#Хранение иерархических деревьев. (48172 hits)
#Передача данных из основного во всплывающее-popup окно через POST. (109982 hits)
#Преобразование RGB в HEX и обратно HEX в RGB. (51317 hits)


Главная >> Каталог задач >> Сортировка >> шелла >> Сортировка Шелла, оптимальный выбор приращений

<< назад
распечататьобсудить >>


Сортировка Шелла, оптимальный выбор приращений
реализации: C++, количество: 4

Aвтор: this
Дата: 19.11.2002
Просмотров: 181224
Рейтинг: 3/7,4.9(3865)
реализации(исходники) +добавить

[Если вы не знакомы с сортировкой Шелла как таковой, то быстрей прочитайте задачу сортировка Шелла, общий принцип]

Приращение в сортировке Шелла - это расстояние между сортируемыми элементами динамически меняющееся на каждом проходе. Главное требование, чтобы на последней итерации оно было равно 1. Динамика изменения этой величины очень существенно сказывается на производительности алгоритма в целом.

Очевидно, что программист может выбрать любой алгоритм уменьшения этого приращения на каждом шаге, главное, чтобы в конце оно приняло значение 1. Существует немало стратегий рассчета приращения на каждом проходе алгоритма Шелла.

Например, Р. Седжвик, предложил такую схему вычисления прирашений:
d[i] = 9*2i - 9*2i/2 + 1, если i четно
d[i] = 8*2i - 6*2(i+1)/2 + 1, если i нечетно

Было доказано, что используя эту схему производительность алгоритма возрастает ~ O(n7/6) в среднем и до ~ O(n4/3) в худшем случае. При расчете приращений по этому методу останавливаться следует на значении d[i-1], если 3*d[i] > n. Обычно расчет начинается с нулевых значений i(=[0,1,2...]) и продолжается до такого i, когда 3*d[i+1] > n, как было сказано ранее. Т.о. данная процедура рассчета запускается перед самой сортировкой Шелла и затем хранит полученную таблицу приращений в памяти, а алгоритм сортировки на каждом шаге к ней обращается за очередным значением.

Например, пусть имеем последовательность из n=35 элементов. Тогда:
Dsedj[0] = 1, Dsedj[1] = 5, Dsedj[2] = 19. Поскольку 3*19 > 35, останавливаемся на значении 5, получая последовательность приращений для данного n=35:[1,5]. Т.е. всего лишь 1 и 5. В базовой реализации мы бы имели:[17, 8, 4, 2, 1].

Алгоритм расчета приращений Седжвика будет иметь вид:

 псевдокод: расчет приращений шелла методом Р. Седжвика  ссылка
  1. p1 = p2 = p3 = 1
  2. i = -1;
  3. loop
  4. if (++i % 2)
  5. d[i] = 8*p1 - 6*p2 + 1
  6. else
  7. d[i] = 9*p1 - 9*p3 + 1
  8. p2 *= 2
  9. p3 *= 2
  10.  
  11. p1 *= 2
  12. if 3*d[i] >= n
  13. break
  14.  
  15. if i > 0
  16. return --i
  17.  
  18. return 0


Cуществует другое мнение: для достаточно больших массивов рекомендуемой можно считать последовательность таких di, что:
di+1 = 3di + 1;
т.е., последовательность включает по порядку приращения: ..., 364, 121, 40, 13, 4, 1. Начинается процесс с dm-2, где m - наименьшее целое, такое, что dm >= n;

Для нашего случая с n=35 получим: d=[1,4], поскольку h3=40 > n=35 => imax = 3-1 = 1

Алгоритм рассчета таких приращений имеет вид:

 псевдокод: рассчет приращений оптимальных для больших сортируемых последовательностях  ссылка
  1. i = 0
  2. d[0] = 1
  3.  
  4. while (d[i] < n)
  5. i++
  6. d[i] = 3*d[i-1] + 1
  7.  
  8. if i < 2
  9. return 0
  10.  
  11. return i-2




Реализации: C++(4)   +добавить реализацию

1) Сортировка Шелла с приращениями по Седжвику и последним "пузырьковом" проходе, code #20[автор:this]
2) Сортировка Шелла с приращениями для больших размерностей и последним "пузырьковом" проходе, code #21[автор:this]
3) Модификация базовой сортировки Шелла с приращениями по методу Р. Седжвика, code #22[автор:this]
4) Модификация базовой сортировки Шелла с приращениями для больших N, code #23[автор:this]


<< назад наверх
распечататьобсудить >>

каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2021 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.016996 секунд
Количество запросов к БД: 14, gzip: off