Методы сортировок Опции

[virt]

Описание и реализация алгоритмов:

• Пузырьковая сортировка (простым выбором, простым обменом, линейная)
• Пузырьковая сортировка с просеиванием
• Сортировка простой вставкой
• Сортировка слияниями
• Быстрая сортировка Хоара
• Пирамидальная - турнирная - HeapSort сортировка
• Распределяющая сортировка - RadixSort - цифровая - поразрядная
• Древесная сортировка (TreeSort)
• Сортировка методом поиска нового номера
• Метод последовательного поиска минимумов

****** ******

Сравнительная скорость работы некоторых нижеприведенных алгоритмов сортировки:



Примечание:

size: размер сортируемой последовательности
n: количество сортировок для замера времени
*: RadixSort в последнем тесте прогонялся при параметрах: size=21000; n=100

[volvo]

Сортировка слияниями

Type
  arrType = Array[1 .. n] Of Integer;

Procedure merge(Var ar: arrType; n: Integer);

  Procedure Slit( k, q: Integer );
  Var
    m: Integer;
    i, j, T: Integer;
    d: arrType;
  Begin
    m := k + (q-k) div 2;
    i := k; j := Succ(m); t := 1;
    While (i <= m) and (j <= q) Do Begin
      If ar[i] <= ar[j] Then Begin
        d[T] := ar[i]; Inc(i)
      End
      Else Begin
        d[T] := ar[j]; Inc(j)
      End;
      Inc(T)
    End;

    While i <= m Do Begin
      d[T] := ar[i]; Inc(i); Inc(T)
    End;
    While j <= q Do Begin
      d[T] := ar[j]; Inc(j); Inc(T)
    End;

    For i := 1 to Pred(T) Do
      ar[Pred(k+i)] := d[i]
  End;

  Procedure Sort(i, j: Integer);
  Var T: integer;
  Begin
    If i >= j Then Exit;

    If j-i = 1 Then Begin
      If ar[j] < ar[i] Then Begin
        T := ar[i]; ar[i] := ar[j]; ar[j] := T
      End
    End
    Else Begin
      Sort(i, i + (j-i) div 2);
      Sort(i + (j-i) div 2 + 1, j);
      Slit(i, j)
    End;
  End;

Begin
  Sort(1, n);
End;

Сложность О(n*logn), самая быстрая из сортировок, но использует в 2 раза больше оперативной памяти.