Условие
Та же задача, но требуется, чтобы сначала шли элементы,
меньшие
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;
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
1 |
|
Название |
Переменные, выражения, присваивания |
|
параграф |
|
Номер |
2 |
|
Название |
Массивы |
|
задача |
|
Номер |
1.2.32 |
