(*~\Глагол\Приложения\Упорядочивание\~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
(**)                           ОТДЕЛ ОбменомБ;
(*============================================================================*
 * НАЗНАЧЕНИЕ: упорядочивание ряда быстрым обменом ("быстрая сортировка")
 *============================================================================*)

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА Упорядочить-(ряд+:РЯД ИЗ ЦЕЛ);
(*
 * Цель:  упорядочивание с помощью разделения на участки (Ч.Хоар)
 * До:    <ряд> - исходный ряд
 * После: <ряд> - упорядоченный ряд
 *)
ПЕР
  Л,П:ЦЕЛ;                          (* текущий участок                   *)
  л,п:ЦЕЛ;                          (* новый участок                     *)
  граница:ЦЕЛ;                      (* граничное значение для разделения *)
  рядл:ЦЕЛ;                         (* промежуточное значение для обмена *)
  глубина:ЦЕЛ;                      (* текущая глубина стека             *)
  стек:РЯД 32 ИЗ НАБОР Л,П:ЦЕЛ КОН; (* стек для новых участков *)
УКАЗ
  глубина:=0; 
  стек[0].Л:=0; 
  стек[0].П:=РАЗМЕР(ряд)-1;
  ПОВТОРЯТЬ
                                         (* выбор из стека последнего запроса *)
    Л:=стек[глубина].Л; 
    П:=стек[глубина].П;
    УМЕНЬШИТЬ(глубина);
    ПОВТОРЯТЬ
                                                (* разделение ряд[Л]...ряд[П] *)
      л:=Л; п:=П;
      граница:=ряд[(Л+П) ДЕЛИТЬ 2];
      ПОВТОРЯТЬ
        ПОКА ряд[л] > граница ВЫП УВЕЛИЧИТЬ(л) КОН;
        ПОКА граница > ряд[п] ВЫП УМЕНЬШИТЬ(п) КОН;
        ЕСЛИ л <= п ТО                               (* обмен ряд[л] с ряд[п] *)
          рядл:=ряд[л];
          ряд[л]:=ряд[п];
          ряд[п]:=рядл;
          УВЕЛИЧИТЬ(л);
          УМЕНЬШИТЬ(п)
        КОН
      ДО л > п;
      ЕСЛИ п-Л < П-л ТО
        ЕСЛИ л < П ТО (* запись в стек запроса на упорядочивание правой части *)
          УВЕЛИЧИТЬ(глубина);
          стек[глубина].Л:=л;
          стек[глубина].П:=П
        КОН;
        П:=п                       (* продолжение упорядочивания  левой части *)
      ИНАЧЕ
        ЕСЛИ Л < п ТО (* запись в стек запроса на упорядочивание  левой части *)
          УВЕЛИЧИТЬ(глубина);
          стек[глубина].Л:=Л;
          стек[глубина].П:=п
        КОН;
        Л:=л                       (* продолжение упорядочивания правой части *)
      КОН
    ДО Л >= П
  ДО глубина < 0
КОН Упорядочить;

КОН ОбменомБ.
