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

Delphi

Двойная сортировка выбором

Попытка усовершествовать классическую сортировку выбором.

На каждом проходе будем находить не только минимальный, но и максимальный элемент.

Тогда на каждом проходе неотсортированная область будет уменьшатся на два элемента. Понадобится вдвое меньше проходов.

Но количество сравнений на каждом проходе удвоится, а количество перестановок останется неизменным.

Как результат, выигрыш получается минимальным, а при неаккуратной реализации Двойная сортировка выбором может оказаться даже медленнее обычной.

type
  TAI = array of integer;
...
procedure DoubleSelectionSort(var A: TAI);
var
    j : integer;
    minV, minI  : integer;
    maxV, maxI  : integer;
    left, right : integer;
begin
  left  := Low(A);
  right := High(A);
  while left<right do
  begin
    minV := A[left];  minI := left;
    maxV := A[right]; maxI := right;
    for j := left to right do
    begin
      if A[j] < minV then
      begin
        minV := A[j];
        minI := j;
      end;
      if A[j] > maxV then
      begin
        maxV := A[j];
        maxI := j;
      end;
    end;
    if minI > left then
    begin
      swap(A[left], A[minI]);
      if maxI = left then maxI := minI;
    end;
    if maxI < right then
    begin
      swap(A[right], A[maxI]);
    end;
    inc(left);
    dec(right);
  end;
end;

 

Сложность:

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

Filtered HTML

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

Plain text

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