4.1. Квадратичные алгоритмы

  •  
      4.1.1. Пусть a[1], ..., a[n] - целые числа. Требуется построить массив b[1], ..., b[n], содержащий те же числа, для которого b[1] <= ... <= b[n].

      Замечание. Среди чисел a[1]...a[n] могут быть равные. Требуется, чтобы каждое целое число входило в b[1]...b[n] столько же раз, сколько и в a[1]...a[n].

      Решение. Удобно считать, что числа a[1]..a[n] и b[1]..b[n] представляют собой начальное и конечное значения массива x. Требование "a и b содержат одни и те же числа" будет заведомо выполнено, если в процессе работы мы ограничимся перестановками элементов x.
      ...
      k := 0;
      {k наименьших элементов массива x установлены на свои места}
      while k <> n do begin
      | s := k + 1; t := k + 1;
      | {x[s] - наименьший среди x[k+1]...x[t] }
      | while t<>n do begin
      | | t := t + 1;
      | | if x[t] < x[s] then begin
      | | | s := t;
      | | end;
      | end;
      | {x[s] - наименьший среди x[k+1]..x[n] }
      | ... переставить x[s] и x[k+1];
      | k := k + 1;
      end;

      4.1.2. Дать другое решение задачи сортировки, использующее инвариант {первые k элементов упорядочены: x[1] <= ... <= x[k]}

      Решение.
      k:=1;
      {первые k элементов упорядочены}
      while k <> n do begin
      | t := k+1;
      | {k+1-ый элемент продвигается к началу, пока не займет
      | надлежащего места, t - его текущий номер}
      | while (t > 1) and (x[t] < x[t-1]) do begin
      | | ... поменять x[t-1] и x[t];
      | | t := t - 1;
      | end;
      end;

      Замечание. Дефект программы: при ложном выражении (t > 1) проверка x[t] < x[t-1] требует несуществующего значения x[0].

      Оба предложенных решения требуют числа действий, пропорционального n*n. Существуют более эффективные алгоритмы.