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

[virt]

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

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

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

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



Примечание:

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

[virt]

Пузырьковая сортировка (простым выбором, простым обменом, линейная)

Последовательно просматривая числа a₁ , ... , a_n находим наименьшее i такое, что a_i > a_i+1 . Меняем a_i и a_i+1 местами, продолжаем просмотр с элемента a_i+1 и т.д. Тем самым наибольшее число передвинется на последнее место. Следующие просмотры начинать со второго элемента, при этом количество просматриваемых элементов уменьшится на единицу. Массив будет упорядочен после просмотра, в котором участвовали только элементы a_n-1 и a_n.

Скачать:

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

Procedure Bubble(Var ar: arrType; n: integer);
Var i, j, T: Integer;
Begin
  For i := 1 To n Do
    For j := n DownTo i+1 Do
      If ar[Pred(j)] > ar[j] Then Begin { < }
        T := ar[Pred(j)]; ar[Pred(j)] := ar[j]; ar[j] := T
      End
End;

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

Const
  n = 10;

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

Const
  a: arrType =
       (7, 1, 9, 8, 5, 6, 2, 4, 3, 10);


Procedure Bubble(Var source, sorted: arrType);

  Procedure SwapIndex(i, j: Integer);
    Var
      T: TType;
    Begin
      move(sorted[i], T, SizeOf(TType));
      move(sorted[j], sorted[i], SizeOf(TType));
      move(T, sorted[j], SizeOf(TType));
    End;

  Var
    i, j: Integer;
  Begin
    move(source, sorted, SizeOf(arrType));
    For i := 1 To n Do
      For j := n DownTo i + 1 Do
        If sorted[Pred(j)] < sorted[j] { change here }
          Then SwapIndex(Pred(j), j);
  End;

Var
  b: arrType;
  i: Integer;

Begin
  Bubble(a, b);
  for i := 1 to n do writeln(b[i]);
End.

Реализация пузырьковой сортировки на ассемблере:

procedure BubbleSort(Mas: Pointer; Len: LongWord);
asm
  dec   Len
@CycleExt:
  xor   ebx,ebx
  mov   ecx,Len
  mov   esi,0
@CycleIn:
  mov   edi,Mas[esi]
  cmp   edi,Mas[esi+4]
  jg    @Exchange
  add   esi,4
  loop  @CycleIn
  jmp   @Check
@Exchange:
  mov   ebx,Mas[esi+4]
  mov   Mas[esi+4],edi
  mov   Mas[esi],ebx
  add   esi,4
  loop  @CycleIn
@Check:
  cmp   ebx,0
  je    @Exit
  jmp   @CycleExt
@Exit:

end;

Сложность этого метода сортировки составляет О(n^2)

Сообщение отредактировано: klem4 - 2.12.2007 16:04