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

Delphi

Сортировка перестановками

Посмотрим на сортировку как на комбинаторную задачу. Просто переберём все возможные перестановки исходного массива, пока не найдём отсортированный вариант.

type
  TAI = array of integer;
...
procedure PermutationSort(var A: TAI);

  function IsSorted: boolean;
  var
      i: integer;
  begin
    result := true;
    for i:= High(A)-1 downto 0 do
    begin
      if A[i] > A[i+1] then
      begin
        result := false;
        break;
      end;
    end;
  end;

  function PermSort(Index: integer): boolean;
  var
      i: integer;
  begin
    if IsSorted then
      result := true
    else begin
           result := false;
           for i:= Index to High(A) do
           begin
             swap(A[Index], A[i]);
             if PermSort(Index+1) then
             begin
               result := true;
               Exit;
             end;
             swap(A[Index], A[i]);
           end;
         end;
  end;
begin
  PermSort(0);
end;

Сложность:

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

Filtered HTML

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

Plain text

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