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

[virt]

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

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

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

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



Примечание:

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

[klem4]

Сортировка методом поиска нового номера (в новый массив)

Краткая теория: Последовательно для каждого элемента массива вычисляется его новая позиция в отсортированном массиве, рассчитывается кол-во элементов, значения которых

1. < значения анализируемого
2. значения которых = значению анализируемого элемента и номера которых <= номера анализируемого.

Особенности: Требуется дополнительный массив, не чувствительный к изначальной упорядоченности.

Оценка числа операций: N*N

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

var
   mass1,NewMass : TArr;
   n : integer;                  

{ 
  n-размерность массива, mass1 - исходный массив,
  NewMass - удет состоять из отсотртированных элементов массива mass1
}

procedure NewNSort(var mass, Nmass: TArr; size: integer); 
var i, j, NewN: integer;
begin
  for i:=1 to size do begin
    NewN:=0;
    for j:=1 to size do
      if (mass[j]<mass[i]) or ((mass[j]=mass[i]) and (j<=i)) then inc(NewN);
      Nmass[NewN]:=mass[i];
  end;
end;

Пример использования:

NewNSort(mass1, NewMass, n);

Массив NewMass будет состоять из элементов массива mass1, но уже отсортированных.
На небольших массивах работает неплохо.

Добавлено:

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

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

Количество тестов: n = 4 000 000
#1: 292 (метод нового номера)
#2: 558 (сортировка пузырьком)
#3: 490 (поразрядная сортировка - radixsort)

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

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

На небольших массивах действительно достаточно быстрый метод, но с увеличением размера массива "метод нового номера" начинает значительно проигрывать поразрядной сортировке.

volvo