Задача 76263
|
|
 |
Условие
Та же задача, но требуется, чтобы сначала шли элементы,
меньшие b, затем равные b, а лишь затем
большие b.
Решение
Теперь потребуются три границы: до первой будут идти элементы, меньшие b, от первой до второй — равные b, затем неизвестно какие до третьей, а после третьей — большие b. (Более симметричное решение использовало бы четыре границы, но вряд ли игра стоит свеч.) В качестве очередного рассматриваемого элемента берём элемент справа от средней границы.
l:=0; m:=0; r:=n;
{инвариант: a[1..l]<b; a[l+1..m]=b; a[r+1]..a[n]>b}
while m <> r do begin
| if a[m+1]=b then begin
| | m:=m+1;
| end else if a[m+1]>b then begin
| | ..обменять a[m+1] и a[r]
| | r:=r-1;
| end else begin {a[m+1]<b}
| | ..обменять a[m+1] и a[l+1]
| | l:=l+1; m:=m+1;
| end;
end;
