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

Delphi

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

Усовершенствование сортировки простыми вставками, в которой для поиска места вставки используектся бинарный поиск.

type
  TAI = array of integer;
...
procedure InsertionWithBSearchSort(var A: TAI);
var
    i, j: integer;
    left, right, mid: integer;
    value: integer;
begin
  for i := Low(A)+1 to High(A) do
  begin
    left := Low(A);
    right := i;
    while left<right do
    begin
      mid := (left+right) div 2;
      if A[i]<A[mid] then right := mid
                     else left  := mid + 1;
    end;
    value := A[i];
    for j := i-1 downto left do
      A[j+1] := A[j];
    A[left] := value;
  end;
end;

 

Сложность:

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

 

Filtered HTML

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

Plain text

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