Учебники

Структура данных и алгоритмы — Shell Sort

Декабрь 12, 2018

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

Этот алгоритм использует сортировку вставки для широко распространенных элементов, сначала сортируя их, а затем сортирует менее широко расположенные элементы. Этот интервал называется интервалом . Этот интервал рассчитывается на основе формулы Кнута как —

Формула Кнута 

h = h * 3 + 1
where −
   h is interval with initial value 1

Этот алгоритм достаточно эффективен для наборов данных среднего размера, поскольку его средняя и наихудшая сложности этого алгоритма зависят от последовательности промежутков, наиболее известной из которых является Ο (n), где n — количество элементов. И в худшем случае сложность пространства O (n).

Как работает Shell Sort?

Давайте рассмотрим следующий пример, чтобы понять, как работает сортировка оболочки. Мы берем тот же массив, который мы использовали в наших предыдущих примерах. Для нашего примера и простоты понимания мы берем интервал 4. Составьте виртуальный подсписок всех значений, расположенных с интервалом в 4 позиции. Вот эти значения: {35, 14}, {33, 19}, {42, 27} и {10, 44}

Shell Sort

Мы сравниваем значения в каждом подсписке и меняем их (при необходимости) в исходном массиве. После этого шага новый массив должен выглядеть так:

Shell Sort

Затем мы берем интервал 1, и этот разрыв генерирует два подсписка — {14, 27, 35, 42}, {19, 10, 33, 44}

Shell Sort

Мы сравниваем и меняем значения, если необходимо, в исходном массиве. После этого шага массив должен выглядеть так:

Shell Sort

Наконец, мы сортируем остальную часть массива, используя интервал значения 1. Сортировка оболочки использует сортировку вставкой для сортировки массива.

Ниже приводится пошаговое описание —

Shell Sort

Мы видим, что для сортировки остальной части массива потребовалось всего четыре перестановки.

Алгоритм

Ниже приведен алгоритм сортировки оболочки. 

Step 1 − Initialize the value of h
Step 2 − Divide the list into smaller sub-list of equal interval h
Step 3 − Sort these sub-lists using insertion sort
Step 3 − Repeat until complete list is sorted

ПСЕВДОКОД

Ниже приведен псевдокод для сортировки оболочки. 

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   while interval > 0 do:

      for outer = interval; outer < A.length; outer ++ do:

      /* select value to be inserted */
      valueToInsert = A[outer]
      inner = outer;

         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner - interval]
            inner = inner - interval
         end while

      /* insert the number at hole position */
      A[inner] = valueToInsert

      end for

   /* calculate interval*/
   interval = (interval -1) /3;	  

   end while
   
end procedure

Чтобы узнать о реализации сортировки оболочки на языке программирования C, пожалуйста, нажмите здесь .

147
Share: