<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Сортировка Шелла, обший принцип
Исходник: Базовая сортировка Шелла без результирующей сортировки [C++, code #24, hits: 5785, рейтинг: 3/7,4.84(2829)] +
автор: this [добавлен: 31.01.2006] управление:
  1. template<class T>
  2. void ShellSortBin2(T* x) {
  3. int d = n, i, j;
  4. while (d > 0) {
  5. d /= 2;
  6.  
  7. /* Данный цикл представляет собой
  8. 1 "пузырьковый" проход по всем группам элементов
  9. на данном шаге. Кроме того, здесь, он выполняется
  10. и в конце, когда d=1, позволяя избежать результирующей
  11. сортировки */
  12. for (i = d; i < n; i++) {
  13. T tmp = x[i];
  14. for (j = i-d; (j >= 0) && (x[j] > tmp); j -= d) {
  15. x[j+d] = x[j];
  16. }
  17. x[j+d] = tmp;
  18. }
  19. }
  20. }
Приращение на каждом шаге - уменьшается вдвое.
Результирующая сортировка не выполняется поскольку для конечной последовательности Шелла, т.е. когда d=1 и имеются 2 отсортированные группы элементов - к этой последовательности был также применен проход "пузырька", окончательно расставляющий элементы по своим местам.

Производительность: менее ~ O(n2)
Расход памяти: - (только на счетчики цикла, доп. переменные и проч.)
При этом следует отметить, что расход памяти меньше чем в базовом варианте, т.к. не запускается фукнция результирующей сортировки и swap также не используется.

+добавить реализацию
 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2018 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.005709 секунд
Количество запросов к БД: 9, gzip: 3.4kb/9.3kb(64%)