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

[virt]

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

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

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

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



Примечание:

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

[klem4]

Пузырьковая сортировка с просеиванием

Аналогичен методу пузырьковой сортировки, но после перестановки пары соседних элементов выполняется просеивание: наименьший левый элемент продвигается к началу массива насколько это возможно, пока не выполняется условие упорядоченности.

Преимущество: простой метод пузырька работает крайне медленно, когда мин/макс (в зависимости от направления сортировки) элемент массива стоит в конце, этот алгоритм - намного быстрее.

const n = 10;
var
  x: array[1 .. n] of integer;
  i, j, t: integer;
  flagsort: boolean;

procedure bubble_P;
begin
  repeat
    flagsort:=true;
    for i:=1 to n-1 do
      if not(x[i]<=x[i+1]) then begin
        t:=x[i];
        x[i]:=x[i+1];
        x[i+1]:=t;
        j:=i;

        while (j>1)and not(x[j-1]<=x[j]) do begin
          t:=x[j];
          x[j]:=x[j-1];
          x[j-1]:=t;
          dec(j);
        end;
        flagsort:=false;
      end;
  until flagsort;
end;

Добавлено:

Тестировалось на массиве целых чисел (25000 элементов).
Прирост скорости относительно простой пузырьковой сортировки - около 75%...

volvo