--- все числа меньше x
--- всякие числа (т.е. какие-то больше, какие-то меньше)
--- все числа больше или равны x
наша задача - расширять две крайние области, чтобы средняя пропала
для начала смотрим, что за число стоит сразу после первой области, если оно меньше x, то можно смело удлинить первую область на 1
потом - на число сразу перед третьей областью, если оно больше или равно - аналогично
если же ни то, ни другое не верно, то просто меняем эти элементы местами и получается, что можно удлинить обе области
пример:
(жирным показаны первая и третья области)
7 3 9 2 10 4 8 1 5 6 (x=4)
7 3 9 2 10 4 8 1 5 6 (заметили, что 6-ка стоит в правильной части)
7 3 9 2 10 4 8 1 5 6 (5-ка тоже)
1 3 9 2 10 4 8 7 5 6 (и 7, и 1 выбиваются, значит меняем, и они переходят в свои части)
1 3 9 2 10 4 6 7 5 6
1 3 9 2 10 4 6 7 5 6
1 3 9 2 10 4 6 7 5 6
1 3 9 2 10 4 6 7 5 6 (т.к. 4>=x)
1 3 9 2 10 4 6 7 5 6
1 3 2 9 10 4 6 7 5 6
1 3 2 9 10 4 6 7 5 6
Цитата(Foxon @ 6.1.2007, 20:00  ) |
| но 4 не должна сдвигаться... |
привязка идёт не к опорному элементу, а к опорному значению, его индекс до упорядочивания абсолютно неважен
иногда, например, в качестве опорного выбирают значение первого элемента
в этом случае проблематично обойтись без его передвижения...