Добрый день. Сегодня, как и обещал о сортировке. В прошлом выпуске я давал задачу, но никому не захотелось её решать, поэтому задачи будут даваться в случае крайней необходимости. Также прошу написать свои отзывы и предложение: что непонятно, о чём надо поподробней, а о чём и вовсе не надо.

O-нотация.
 Начиная разговор о сортировке, хотелось бы вспомнить о прошлых выпусках. В них мы изучили два метода для эмпирического анализа алгоритмов. Подходя к теме сортировке хотелось бы отметить один теоретический метод анализа, называемый O-нотацией(big-Oh notation).Это специальная математическая функция от n(количество элементов). Говорят, что алгоритм принадлежит к классу O(f(n)), f(n) - это какая-либо функция. Более просто, можно сказать, что быстродействие алгоритма пропорционально f(n). Примеры:
 1. Пример очень условен. Вам надо подсчитать сумму элементов массива. Для этого вам надо обойти все элементы. Следовательно, мы можем предположить, что алгоритм относится к классу O(n) - линейный. На практике - это один цикл, с числом итераций n.
 2. Допустим, Вы экспереминтально установили, что алгоритм принадлежит к классу O(n³+n). При сравнительно больших n мы заметим, что влияние +n очень незначительное(n³поглощает +n). Следовательно при больших n, O(n³+n) эквивалентно O(n³).
Использование O-нотации предполагает, что мы имеем дело с довольно большими значениями n.
Сортировка
Начнём с пузырьковой сортировки(bubble sort).
Эта самая известная сортировка и в то же время самая медленная.
Давайте разбираться на примере:
Допустим у нас имеется 7 чисел, которые нужно отсортировать. Сначала мы сравним 7-ое и 6-ое числа, и если 7-ое меньше, то поменяем их местами. Затем мы сравниваем 6-ое и 5-ое, и т. д. После первого прохода, мы видим, что число 29(наименьшее) оказалось на первой позиции, иначе говоря, число 29 "всплыло" на первую позицию. При последующих прохождениях мы уже не обращаемся к первой позиции.

Для конкретного случая: n=7, f(n)=(49-7)/2=21.
При больших n, O((n²-n)/2) эквивалентно O(n²).
Пузырьковая сортировка принадлежит к классу O(n²).

Что ж, приступим к реализации.
Чтобы что-то отсортировать, надо найти что-то не отсортированное. Давайте напишем процедуру, генерирующую массив случайных чисел:

procedure IncrementRange(var a:TMyArray;aStart,aEnd:integer);
//Процедура, которая заполняет массив числами
var
 i : integer;
begin
  for i:=aStart to aEnd do
  a[i]:=i-aStart+1;
end;

procedure RandomRange(var a:TMyArray;aStart,aEnd:integer);
//Процедура, которая перетасовывает элементы массива
var
  Range : integer;
  Inx : integer;
  RandomInx : integer;
begin
  IncrementRange(MyArr,aStart,aEnd);
//Заполним массив
  for Inx:=aEnd downto aStart+1 do
//Цикл по всем элементам
  begin
    RandomInx:=aStart+Random(Inx-aStart);
//Случайный номер элемента, от нального до текущего-1
    if RandomInx<>Inx then
//Меняем местами, используя 0 элемент как временную переменную
    begin
      a[Low(a)]:=a[Inx];
      a[Inx]:=a[RandomInx];
      a[RandomInx]:=a[Low(a)];
    end;
  end;
end;

Собственно как это работает:

0)	1	2	3	4	5	6	7	8	9	10
1)	1	2	3	4	5	6	7	8	10	9
2)	1	10	3	4	5	6	7	8	2	9
3)	1	10	3	8	5	6	7	4	2	9
4)	1	7	3	8	5	6	10	4	2	9
5)	1	7	3	6	5	8	10	4	2	9
6)	1	7	5	6	3	8	10	4	2	9
7)	6	7	1	5	3	8	10	4	2	9
end)	6	7	1	5	3	8	10	4	2	9

Перейдём к основной теме, реализуем процедуру сортировки:

const
  MaxLength=10;
type
  TMyArray=array[0..MaxLength] of integer;
var
  MyArr : TMyArray;
{...............}
procedure BubbleSort(var a:TMyArray; aStart,aEnd:integer);
var
  i,j : integer;
  Stop : boolean;
begin
  for i:=aStart to pred(aEnd) do
  begin
    Stop:=true;
    for j:=aEnd downto succ(i) do
    begin
      if a[j-1]>a[j] then
      begin
        a[Low(a)]:=a[j];
        a[j]:=a[j-1];
        a[j-1]:=a[Low(a)];
        Stop:=false;
      end;
    end;
    if Stop then exit;
  end;
end;
Код полностью я не привожу. Если будут вопросы, то пишите.

Хотелось бы рассмотреть одну модификацию пузырьковой сортировки - Шейкер-сортровка(shaker sort).
При её реализации требуется чередовать направление проходов.

Так как пузырьковая сортировка относится к алгоритмам класса O(n²), то при увеличении числа элементов в 2 раза, длительность увеличивается в 4 раза. Приведу таблицу моих замеров. Значения в мс.

Кол-во	16	32	64	128	256	512	1024	2048	4096	8192	16384	32768	65536
Bubble	0.0025	0.0085	0.0323	0.1293	0.5214	2.0936	8.3018	32.793	130.88	532.87	2151.6	8685.4	47761
Shaker	0.0025	0.0080	0.0282	0.1092	0.4288	1.6955	6.7565	26.718	106.15	426.11	1716.6	6896.2	30936