Вторник, 19.03.2024, 12:11
Приветствую Вас, Гость |
Меню сайта
Наш опрос
Нужен ли форум на этом сайте?
Всего ответов: 1296
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

Сортировка Шелла

        Сортировка методом Шелла базируется на уже известном нам алгоритме простых вставок.
Смысл ее состоит в раздельной сортировке методом простых вставок нескольких частей, на которые разбивается исходный массив. Эти разбиения помогают сократить количество пересылок:
üдля того, чтобы освободить "правильное" место для очередного элемента, приходится уже сдвигать меньшее количество элементов.
Сортировку Шелла придумал Дональд Л. Шелл.
Ее необычность состоит в том, что она рассматривает весь список как совокупность перемешанных подсписков.
На первом шаге эти подсписки представляют собой просто пары элементов.
На втором шаге в каждой группе по четыре элемента.
При повторении процесса число элементов в каждом подсписке увеличивается, а число подсписков, соответственно, падает.
Сортирует элементы массива А[1..n] следующим образом:
Øна первом шаге упорядочиваются элементы n/2 пар (A[i], А[n/2 + i]) для 1 < i < n/2,
Øна втором шаге упорядочиваются элементы в n/4 группах из четырех элементов ( A[i], A[n/4 + i], A[n/2 + i], A[3n/4 + i]) для 1 < i < n/4,
Øна третьем шаге упорядочиваются элементы в n/8 группах из восьми элементов и т.д.;
Øна последнем шаге упорядочиваются элементы сразу во всем массиве А.
На каждом шаге для упорядочивания элементов используется метод сортировки вставками.
Пример реализации сортировки Шелла паскаль:

incr:= n div 2;
   while  incr>0 do
   begin
      for  i:=incr+1 to n do
      begin
        j:= i-incr;
        while  j>0 do
           if A[j]>A[j+incr] then
           begin
              c:= A[j];
              A[j]:=A[j+incr];
              A[j+incr]:=A[j];
              j:=j-incr
           end
           else  j:=0   { останов проверки}
       end;
       incr:= incr div 2
  end;

 
Полный анализ сортировки Шелла чрезвычайно сложен, и мы не собираемся на нем останавливаться.
Было доказано, что сложность этого алгоритма в наихудшем случае при выбранных нами значениях шага равна O(n3/2).
Полный анализ сортировки Шелла и влияния на сложность последовательности шагов можно найти в третьем томе книги Д. Кнута Искусство программирования, М., Мир.


Форма входа
Поиск
Мы в сети
Реклама
Для того чтобы не видеть рекламу в правом верхнем углу сайта пройдите простую процедуру регистрации
ФОРУМ
У нас наконецто появился форум! Добро пожаловать! Будьте первыми, задайте направление форуму! =)
--- Не стесняемся - заходим на форум! ---