Быстрая сортировка

 

Попробуем разбить исходный массив на два подмассива, относительно центрального элемента (назовём его барьером). Сделаем это следующим образом: если текущий элемент больше барьера, то перенесем его вправо иначе влево. По завершении этого процесса массив окажется немного более упорядоченным. Продолжим упорядочение, разбив каждый из уже обработанных подмассивов, ещё на два подмассива и проведём над ними ту же самую операцию. Полностью процесс сортировки окажется завершенным, когда длина подмассивов окажется единичной. Эта сортировка имеет один недостаток. Например, если исходный массив будет изначально полностью или почти полностью упорядоченным, это не уменьшит количество выполняемых операций. Быстрая сортировка всё равно проведет дробление исходного массива до победного конца.

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

§          Выбор элемента барьера (можно середину)

§          Для всех элементов слева от барьера

o         Если значение элемента больше значения – барьера, то переносим его вправо.

§          Для всех элементов справа от барьера

o         Если значение элемента меньше значение – барьера, то переносим его влево.

 

Алгоритм

 

§          ОТРЕЗОК = весь исходный массив

§          Вызов процедуры БЫСТРАЯ СОРТИРОВКА

 

Процедура БЫСТРАЯ СОРТИРОВКА (ЛЕВАЯ ГРАНИЦА, ПРАВАЯ ГРАНИЦА)

 

 

§          Если ЛЕВАЯ меньше ПРАВОЙ то

o         Определяем БАРЬЕР как середину между левой и правой

o         Для всех элементов между ЛЕВОЙ и БАРЬЕРОМ делать

§          Если ОЧЕРЕДНОЙ элемент больше БАРЬЕРА то ОЧЕРЕДНОЙ перекинуть вправо от БАРЬЕРА.

o         Для всех элементов между ПРАВОЙ и БАРЬЕРОМ делать

§          Если ОЧЕРЕДНОЙ элемент меньше БАРЬЕРА то ОЧЕРЕДНОЙ перекинуть влево от БАРЬЕРА.

o         БЫСТРАЯ СОРТИРОВКА(ЛЕВАЯ, БАРЬЕР)

o         БЫСТРАЯ СОРТИРОВКА(БАРЬЕР, ПРАВАЯ)

 

 

Текст программы:

 

MODULE example;

 IMPORT In, StdLog;

 VAR

  a:ARRAY 100 OF INTEGER;

PROCEDURE QuickSort(Left, Right:INTEGER);

VAR

  c,Middle,k,i:INTEGER;

  flag:BOOLEAN;

BEGIN

 IF Right-Left=1 THEN

   IF a[Left]>a[Right] THEN

     c:=a[Left]; a[Left]:=a[Right];a[Right]:=c;

   END;

 ELSE

   Middle:=(Left+Right) DIV 2;

   k:=Left;

   WHILE k<=Right DO

     flag:=TRUE;

     IF (a[k]>a[Middle]) & (k<Middle) THEN

            c:=a[k];

            FOR i:=k TO Middle-1 DO

              a[i]:=a[i+1]

            END;

            a[Middle]:=c;

            Middle:=Middle-1;

            flag:=FALSE;

            k:=k-1;

     END; 

     IF flag & (a[k]<a[Middle]) & (k>Middle) THEN

            c:=a[k];

            FOR i:=k TO Middle+1 BY -1 DO

              a[i]:=a[i-1];

            END;

            a[Middle]:=c;

            Middle:=Middle+1;

     END;

     k:=k+1;

   END; 

   IF Middle>Left THEN

     QuickSort(Left,Middle);

   END;

   IF Middle<Right THEN

     QuickSort(Middle,Right);

   END;

 END;

END QuickSort;

PROCEDURE Sort*;

VAR

  N,i,k,j,c:INTEGER;

BEGIN

 N:=-1;

 In.Open;

 REPEAT

   N:=N+1;

   In.Int(a[N]);

 UNTIL ~In.Done;

 QuickSort(0,N-1);

 FOR i:=0 TO N-1 DO

   StdLog.Int(a[i]);

 END;

END Sort;

END example.