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

Delphi

MSD-сортировка

Most Significant Digit - комбинация блочной и поразрядной сортировки, начиная со старших разрядов.

Считаем все числа дополненными слева нулями до одинаковой длины. Разделим числа на блоки по N бит. Воспользуемся блочной сортировкой, а в качестве хэш-функции используем значение в текущем блоке. На верхнем уровне - N старших бит, на втором - N следующих и т.д.

type
  TAI = array of integer;
...
procedure MSDSort(var A: TAI);
const
      N = 8; // Количество бит в маске.
var
    i : integer;
    Bucket: TList<integer>;
    Mask : integer; // Маска
    MV   : integer; // Необходимое количество проходов сортировки.

    procedure _bucketSort(ABucket: TList<integer>; Iteration: integer);
    var
        i,ii,j : integer;
        buckets : array of TList<integer>;

        // Опаределяем номер корзины по значению и номеру прохода
        function GetIndex(Value, Iteration: integer):integer;
        begin
          result := (Value shr (N * (MV-1-Iteration))) and Mask;
        end;

    begin
      if Iteration<MV then
      begin
        // Создаём нужное количество корзин
        SetLength(buckets, 1 shl N);
        for i := Low(buckets) to High(buckets) do
          buckets[i] := TList<integer>.Create;
        // Раскладываем входные данные по корзинам.
        for i:= 0 to ABucket.Count-1 do
          buckets[GetIndex(ABucket.Items[i], Iteration)].Add(ABucket.Items[i]);
        // Корзины, в которых больше одного элемента,
        //  отсортируем рекурсивно.
        for i := Low(buckets) to High(buckets) do
        begin
          if buckets[i].Count > 1 then
            _bucketSort(buckets[i], Iteration+1);
        end;
        // Соберём значения обратно.
        j :=0;
        for i := Low(buckets) to High(buckets) do
        begin
          for ii := 0 to buckets[i].Count-1 do
          begin
            ABucket[j] := buckets[i].Items[ii];
            inc(j);
          end;
        end;
        // Освободим память из под корзин.
        for i := Low(buckets) to High(buckets) do
          buckets[i].Free;
      end;
    end;

begin
  Mask := 1 shl N - 1;   // Маска заполнена единицами
  MV := (SizeOf(A[0])*8 + N - 1) div N; // Необходимое количество проходов.
// Создаём стартовую корзину.
  Bucket := TList<integer>.Create;
  for i := Low(A) to High(A) do
    Bucket.Add(A[i]);
// Запускаем сортировку.
  _bucketSort(Bucket, 0);
// Забираем результат.
  for i := 0 to Bucket.Count-1 do
    A[i] := Bucket.Items[i];
  Bucket.Free;
end;

Сложность:

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

 

Filtered HTML

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

Plain text

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