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


$\scriptstyle{\blacktriangleright}$ 4.1.1. Пусть ${\hbox{\tt a[1]}},\ldots,{\hbox{\tt a[n]}}$ -- целые числа. Требуется построить массив ${\hbox{\tt b[1]}},\ldots,{\hbox{\tt b[n]}}$, содержащий те же числа, для которого ${\hbox{\tt b[1]}}\leqslant\ldots\leqslant{\hbox{\tt b[n]}}$.

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

Решение.  $\!\!\!$Удобно считать, что числа ${\hbox{\tt a[1]}}\ldots{\hbox{\tt a[n]}}$и ${\hbox{\tt b[1]}}\ldots{\hbox{\tt b[n]}}$ представляют собой начальное и конечное значения массива x. Требование <<a и b содержат одни и те же числа>> будет заведомо выполнено, если в процессе работы мы ограничимся перестановками элементов x. 
  k := 0;
  {k наименьших элементов массива установлены на свои места}
  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;`


$\scriptstyle{\blacktriangleright}$ 4.1.2. Дать другое решение задачи сортировки, использующее инвариант << первые k элементов упорядочены>> (${\hbox{\tt x[1]}}\leqslant\ldots\leqslant{\hbox{\tt 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) проверка ${\hbox{\tt x[t]}}<{\hbox{\tt x[t-1]}}$ требует несуществующего значения x[0]. 


Оба предложенных решения требуют числа действий, пропорционального ${\hbox{\tt n}}^2$. Существуют более эффективные алгоритмы.


pvv
1/8/1999