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

Delphi

Сортировка вставками

Берём исходные элементы и складываем в результат в отсортированном порядке. Для каждого нового элемента в результате находим правильное место и вставляем, раздвигая результат.

Сортировать будем начало массива, текущий элемент будем менять местами с предыдущим, пока он не займет правильного места. Так мы одновременно реализуем и поиск нужной позиции, и вставку.

procedure InsertionSort(var A: TAI);
var
    i, j: integer;
begin
  for i := Low(A)+1 to High(A) do
  begin
    j := i;
    while (j > Low(A)) and (A[j] < A[j-1]) do
    begin
      swap(A[j], A[j-1]);
      dec(j);
    end;
  end;
end;

 

Сложность:

Максимальная 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-теги не обрабатываются и показываются как обычный текст
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и абзацы переносятся автоматически.