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

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

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

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

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

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

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;

Сложность: