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

[virt]

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

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

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

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



Примечание:

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

[klem4]

Метод последовательного поиска минимумов

Теория: Просматривается весь массив, ищется минимальный элемент и ставится на место первого, "старый" первый элемент ставится на место найденного

type
  TArr = array[1..100] of integer;

var
  mass1 : TArr;
  n : integer;       

procedure NextMinSearchSort(var mass:TArr; size:integer);
var i, j, Nmin, temp: integer;
begin
  for i:=1 to size-1 do begin
    nmin:=i;
    for j:=i+1 to size do
      if mass[j]<mass[Nmin] then Nmin:=j;

    temp:=mass[i];
    mass[i]:=mass[Nmin];
    mass[Nmin]:=temp;
  end;
end;

Вызов:

NextMinSearchSort(mass1, n);

Добавлено:

Тесты на скорость (в условных единицах):

1. (набор данных - массив из 15 элементов типа integer)

Количество тестов: n = 1 000 000
#1: 159 (метод нового номера)
#2: 127 (поразрядная сортировка - radixsort)
#3: 61 (метод поиска минимумов)

2. (набор данных - массив из 800 элементов типа integer)

Количество тестов: n = 225
#1: 107 (метод нового номера)
#2: 1 (поразрядная сортировка - radixsort)
#3: 25 (метод поиска минимумов)

3. (набор данных - массив из 10000 элементов типа integer)

Количество тестов: n = 9
#1: 597 (метод нового номера)
#2: 2 (поразрядная сортировка - radixsort)
#3: 147 (метод поиска минимумов)

volvo