Структура данных и алгоритмы - Сортировка оболочки

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

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

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

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

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

Как работает сортировка оболочки?

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

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

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

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

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

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

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

Алгоритм

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

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, щелкните здесь .