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

Delphi

Прямое слияние Боуза-Нельсона

Разделим массив пополам. Проведём слияние. Будем попарно сравнивать элементы и выкладывать в результат в отсортированном порядке(каждый элемент - это отсортированный массив длиной один ). Теперь наша последовательность состоит из сотированных массивов длиной два. Снова разобъём массив пополам, но теперь будем в сеанс слияния брать по два элемента из каждой половины, раз мы можем быть уверены что они сортированы. Теперь результат состоит из сортированных массивов длиной четыре элемента, и на следующем круге можно сливать порции по четыре элемента. Будем продолжать, пока размер сортированного элемента не превысит размер массива.

procedure BoseNelsonSort(var A: TAI);
var
    m: integer;
    j: integer;

    procedure merge(j, r, m : integer);
    begin
      if j+r < length(A) then
      begin
        if m = 1 then
        begin
          if A[j] > A[j+r] then
            swap(A[j], A[j+r]);
        end
          else
        begin
          m := m div 2;
          merge(j, r, m);
          if j + r + m < length(A) then
            merge(j + m, r, m);
          merge(j + m, r - m, m);
        end;
      end;
    end;

begin
  m := 1;
  while m < length(A) do
  begin
    j := 0;
    while j+m < length(A) do
    begin
      merge(j, m, m);
      j := j + m + m;
    end;
    m := m + m;
  end;
end;

Filtered HTML

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

Plain text

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