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

[virt]

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

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

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

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



Примечание:

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

[volvo]

Распределяющая сортировка - RadixSort - цифровая - поразрядная

Пусть имеем максимум по k байт в каждом ключе (хотя за элемент сортировки вполне можно принять и что-либо другое, например слово - двойной байт, или буквы, если сортируются строки). k должно быть известно заранее, до сортировки.

Разрядность данных (количество возможных значений элементов) - m - также должна быть известна заранее и постоянна. Если мы сортируем слова, то элемент сортировки - буква, m = 33. Если в самом длинном слове 10 букв, k = 10. Обычно мы будем сортировать данные по ключам из k байт, m=256.

Пусть у нас есть массив source из n элементов по одному байту в каждом.

Для примера можете выписать на листочек массив source = <7, 9, 8, 5, 4, 7, 7>, и проделать с ним все операции, имея в виду m=9.

1. Составим таблицу распределения. В ней будет m (256) значений и заполняться она будет так:
   

   for i := 0 to Pred(255) Do distr[i]:=0;
   for i := 0 to Pred(n) Do distr[source[i]] := distr[[i]] + 1;

   
   Для нашего примера будем иметь distr = <0, 0, 0, 0, 1, 1, 0, 3, 1, 1>, то есть i-ый элемент distr[] - количество ключей со значением i.
   
   
2. Заполним таблицу индексов:
   

   index: array[0 .. 255] of integer;
   index[0]:=0;
   for i := 1 to Pred(255) Do index[i]=index[i-1]+distr[i-1];

   
   В index[ i ] мы поместили информацию о будущем количестве символов в отсортированном массиве до символа с ключом i.
   Hапример, index[8] = 5 : имеем <4, 5, 7, 7, 7, 8>.
   
   
3. А теперь заполняем новосозданный массив sorted размера n:
   

   for i := 0 to Pred(n) Do Begin
     sorted[ index[ source[i] ] ]:=source[i];
     {
       попутно изменяем index уже вставленных символов, чтобы
       одинаковые ключи шли один за другим:
     }
     index[ source[i] ] := index[ source[i] ] +1;
   End;

Итак, мы научились за O(n) сортировать байты. А от байтов до строк и чисел - 1 шаг. Пусть у нас в каждом числе - k байт.

Будем действовать в десятичной системе и сортировать обычные числа ( m = 10 ).

сначала они в сортируем по младшему на один
беспорядке: разряду: выше: и еще раз:
523 523 523 088
153 153 235 153
088 554 153 235
554 235 554 523
235 088 088 554

Hу вот мы и отсортировали за O(k*n) шагов. Если количество возможных различных ключей ненамного превышает общее их число, то 'поразрядная сортировка' оказывается гораздо быстрее даже 'быстрой сортировки'!

Реализация алгоритма "распределяющей" сортировки:

Скачать:  RDX_SORT.PAS ( 740 байт ) Кол-во скачиваний: 2378

Const
  n = 8;

Type
  arrType = Array[0 .. Pred(n)] Of Byte;

Const
  m = 256;
  a: arrType =
       (44, 55, 12, 42, 94, 18, 6, 67);

Procedure RadixSort(Var source, sorted: arrType);
  Type
    indexType = Array[0 .. Pred(m)] Of Byte;
  Var
    distr, index: indexType;

    i: integer;
  begin
    fillchar(distr, sizeof(distr), 0);
    for i := 0 to Pred(n) do
      inc(distr[source[i]]);

    index[0] := 0;
    for i := 1 to Pred(m) do
      index[i] := index[Pred(i)] + distr[Pred(i)];

    for i := 0 to Pred(n) do
      begin
        sorted[ index[source[i]] ] := source[i];
        index[source[i]] := index[source[i]]+1;
      end;
  end;

var
  b: arrType;
begin
  RadixSort(a, b);
end.