Добавить комментарий

Delphi

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

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

procedure ShellSort(var A: TAI);
var
    step: integer;

  // Расчёска с произвольным шагом
  procedure Comb(step: integer);
  var i,j: integer;
  begin
    i := Low(A)+step;
    while i <= High(A) do
    begin
      j := i;
      while (j > Low(A)) and (A[j] < A[j-step]) do
      begin
        swap(A[j], A[j-step]);
        j := j - step;
      end;
      i := i + step;
    end;
  end;

begin
  step := Length(A) -1;
  repeat
    Comb(step);
    step := step div 2;
  until step < 1;
end;

 

Сложность:

Максимальная O(N2)
Минимальная O(n(log n)2)

Существуют другие варианты выбора шагов, которые существенно влияют на сложность:

  • Последовательность Хиббарда: 2i - 1 ≤ N, i ∈ N
  • Седжвика: di = 9 · 2i - 9 · 2i/2 + 1, для чётных i, di = 8 · 2i - 6 · 2(i+1)/2 + 1, для нечётных i
  • Числа Фибоначчи
  • Последовательность Пратта: 2i · 3j ≤ N/2, i,j ∈ N
  • Эмпирическая последовательность Циура: d ∈ {1, 4, 10, 23, 57, 132, 301, 701, 1750}

Filtered HTML

  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Допустимые HTML-теги: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Строки и абзацы переносятся автоматически.
  • Вы можете цитировать другие сообщения, используя тэг [quote]

Plain text

  • HTML-теги не обрабатываются и показываются как обычный текст
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и абзацы переносятся автоматически.