Словесный алгоритм

1)Устанавливаем левую и правую границу l и r(с какова по какой элемент мы хотим отсортировать) .

2)Находим средний элемент между правой и левой границей x (относительно этого элемента мы будем сортировать наш массив) .

3) Пока индикатор i > индикатора j то:

      а) Теперь (если сортируем по возрастанию) то ищем слева , от среднего элемента x , элемент который >=x
         
      б) А справа элемент который <=x
     
      в) И если индикаторы i и j не пересеклись то меняем местами элементы a[ i ] и a[ j ] и увеличиваем(или уменьшаем) индикаторы i и j

4)   Если индикатор j < правой границы r то запускаем сортировку от этих границ.

5)   И если индикатор j > левой границы l то запускаем сортировку от этих границ.

Скорость алгоритма "Быстрая сортировка" n*log2n

Теперь сам  код:

var a:array [1..1000000] of longint;
    i,n:longint;
 procedure qSort(l,r:longint);
  var i,j,z,x:longint;
 begin
   i:=l;
   j:=r;
   x:=a[(i+j)div 2];{находим  средний элемент}
   repeat
     while a[i]<x do i:=i+1;{ищем слева элемент который >=x }
     while a[j]>x do j:=j-1;{а справа элемент который <=x } 
     if i<=j then begin
                        z:=a[i];
                        a[i]:=a[j];
                        a[j]:=z;
                        i:=i+1;
                        j:=j-1;
                      end; {меняем местами элементы a[i] и a[j] и изменяем индикаторы i и j}
   until (i>j);
   if i<r then qSort(i,r);
   if j>l then qSort(l,j); 
 end;
begin         
 readln(n);
 for i:=1 to n do
  read(a[i]);
 qSort(1,n); {задаём границы сортировки}
 for i:=1 to n do
  write(a[i],' ');
end.

Отредактировано ЯНУш (2011-11-01 08:33:37)