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

Delphi

Сортировка расчёской

Основная проблема пузырька, это "черепахи" - элементы, которые движутся против направления проходов сортировки. В классическом пузырьке сравниваются соседние элементы, и "черепахи" сдвигаются на одну позицию за один проход сортировки. Расчёска пытается решить эту проблему сравнивая не соседние элементы, а расположенные на некотором переменном расстоянии. Сортировка начинается с большого расстояния, которое уменьшается после каждого прохода. Таким образом, "черепахи" получают шанс быстрее занять правильное положение.

type
  TAI = array of integer;
...
procedure CombSort(var A: TAI);
const koef = 1.247; // Коэффициент уменьшения.
var
    i, j, k: Integer;
    step : integer;
begin
  step := trunc(Length(A) / koef); // Начальный шаг сортировки - почти полный массив.
  while step>1 do 
  begin
    // Один проход сортировки
    for i := Low(A) to High(A)-step do
    begin
      if A[i]>A[i+step] then
        swap(A[i], A[i+step]);
    end;
    // уменьшаем шаг
    step := trunc(step / koef);
  end;
  // Шаг уменьшился до 1, дальше обычный пузырёк.
  j := High(A)-1;
  while j> Low(A) do
  begin
    k := Low(A);
    for i := Low(A) to j do
    begin
      if A[i] > A[i+1] then
      begin
        swap(A[i], A[i+1]);
        k := i;
      end;
    end;
    j := k;
  end;
end;

Оптимальное значение коэффициента уменьшения:

1 ( 1 - e-Φ ) 1.247
e - основание натурального логарифма
Ф - золотое сечение

 

Сложность:

Максимальная O(N2)
Минимальная O(N)
Средняя O(N2)

 

Filtered HTML

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

Plain text

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