АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Метод Шелла

Читайте также:
  1. A) Метод опроса
  2. I. Метод стандартизации
  3. I. Методы выбора инновационной политики
  4. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ
  5. I. Основные характеристики и проблемы философской методологии.
  6. I.ЗАГАЛЬНІ МЕТОДИЧНІ ВКАЗІВКИ
  7. II. ВИРУСОЛОГИЧЕСКИЙ МЕТОД
  8. II. Методологічні засади, підходи, принципи, критерії формування позитивної мотивації на здоровий спосіб життя у дітей та молоді
  9. II. Методы прогнозирования и поиска идей
  10. II. Формальная логика как первая система методов философии.
  11. II. Цитогенетический метод
  12. III. Метод, методика, технология

Некоторое улучшение метода сортировки простыми включениями было предложено Д.Шеллом в 1959 году.

Идея метода: Сортируются группы записей, отстоящих друг от друга на заданном расстоянии(8). После сортировки всех таких групп, сортируются группы записей, отстоящих на меньшее расстояние(4) и т.д., пока не дойдём до расстояния равному 1.

Существует формула для расчёта приращений:

n – количество записей;

t – количество приращений;

t=[log 3 n]

t=[log 3 n]-1;

ht=1;

hk -1=3*hk+1,

где h – приращение.

Получаем ряд приращений 1,4,13,40,121…

Пример:

n=27; t=3;

h3=1; h2=4; h1=13.

Пример:

(4),(2),(1) – приращения

44 55 12 42 94 18 6 67 4 - сортировка

 
 

 


44 18 6 42 94 55 12 67 2 - сортировка

 

 

6 18 12 42 44 55 94 67 1 - сортировка

 
 


6 12 18 42 44 55 67 94 результат

 

Затраты, которые требуются для сортировки n элементов с помощью алгоритма Шелла пропорциональны n1,2.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)