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

Delphi

Бинго-сортировка

Развитие сортировки выбором.

На каждом проходе будем находить не только очередной максимум но и максимум для следующего прохода. Это позволяет существенно экономить на сортировке массивов с повторяющимися значениями.

type
  TAI = array of integer;
...
procedure BingoSort(var A: TAI);
var
    maxI : integer;
    maxValue,
    nextvalue : integer;
    i : integer;
begin
  maxI := High(A);
  nextValue := A[maxI];

  for i := maxI-1 downto 0 do
    if A[i] > nextValue then nextValue := A[i];

  while (maxI>0) and (A[maxI] = nextValue) do
    dec(maxI);

  while maxI > 0 do
  begin
    maxValue := nextValue;
    nextValue := A[maxI];
    for i := MaxI - 1 downto 0 do
    begin
      if A[i] = maxValue then
      begin
        swap(A[i], A[maxI]);
        dec(maxI);
      end
        else if A[i] > nextValue
               then nextValue := A[i];
    end;

    while (maxI>0) and (A[maxI] = nextValue) do
      dec(maxI);

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