МОДИФІКОВАНІ МЕТОДИ СОРТУВАННЯ

Головний недолік простих методів - обмін ведеться в основному між сусідними елементами. Тому бажано робити якомога ширші обміни.

Метод Шелла

Метод Шелла (Shell D.L., 1959) - метод сортування включеннями з відстанями, що зменшуються.

Візьмемо для прикладу масив:

60

16

41

06

59

79

34

15

На першому етапі масив уявно ділиться на підмасиви з елементами, що, скажімо, відстоять один від одного на 4 елементи:

1. 60

   59

2. 16

   79

3. 41

   34

4. 06

   15

Кожен з них впорядковується окремо:

1. 59

   60

2. 16

   79

3. 34

   41

4. 06

   15

На другому етапі підмасиви утворюються елементами через один:

1. 59

   34

   60

   41

2. 16

   06

   79

   15

Одержуємо

1. 34

   41

   59

   60

2. 06

   15

   16

   79

Аналіз та експериментальні дослідження методу показують, що цей метод дає кращі результати, якщо розподіл на підмасиви роблять кроками, що не є степенями двійки, а, навпаки, не є множниками один одного,
Рекомендованими є такі послідовності кроків:

У останньому випадку кількість необхідних операцій пропорційна n^6/5 = n^1,2.

Програму методу можна запропонувати у такому варіанті ( [2] ), вона використовується для виконання лабораторнної роботи №2 "Методи сортування масивів".

procedure Shellsort(var a: Items);
var 
  t,i,j,k,s: Integer;
  x: Item;
  m: 1 .. n2;
  h: array [1 .. n2] of Integer;

begin
  t := Trunc(ln(n)/ln(2)-1);
  h[t] := 1;
  for k := t-1 downto 1 do
    h[k] := 2*h[k+1] + 1;

  for m := 1 to t do begin
    k := h[m];
    s := -k;
    for i := k+1 to n do begin
      x := a[i];
      j := i - k;
      if s = 0 then s := -k;
      s := s + 1;
      a[s] := x;
      while x < a[j] do begin
        a[j+k] := a[j];
        j := j - k;
      end;
      a[j+k] := x;
    end;
  end;
end;