сортировка случайными вставками

[maxal]

У Васи есть набор кубиков пронумерованных числами от $1,2,\dots,n$, которые выстоены в ряд в некотором порядке. Вася пытается расставить их в порядке возрастания номеров следующим образом. Найдя некоторый (произвольный) кубик, стоящий не на своем месте, он его вынимает и вставляет его на правильное место, сдвигая остальные кубики, не меняя порядка их следования. Сумеет ли Вася гарантированно закончить сортировку кубиков за конечное время?

(источник)

[ИСН]

Сумеет, если характер его произволения таков, что за конечное время он наткнётся на первый кубик - ведь тот, будучи поставлен на правильное место, остаётся на нём и сводит задачу к $n-1$. (Или последний, то же самое).
А если нет, то нет.

[maxal]

ИСН
Ответ неверный.
Возможно, вы не поняли вопрос. Переформулирую так: возможна ли ситуация, что Вася будет сортировать кубики бесконечно?

[Dandan]

Сумма \sum_i|i-p(i)| не увеличивается, а оставлять её такой же бесконечно мы не сможем, т.к. если эта сумма не меняется, то растёт количество инверсий.

[maxal]

Dandan писал(а):

Сумма \sum_i|i-p(i)| не увеличивается, а оставлять её такой же бесконечно мы не сможем, т.к. если эта сумма не меняется, то растёт количество инверсий.

Это неверно.
Например, в перестановке 42351 при перемещении 4 на свое место получается перестановка 23541 с тем же значением функции \sum_i|i-p(i)|, но меньшем числе инверсий.

[Юстас]

По-моему, ИСН все верно написал: если Вася выбирает кубик наудачу, то ему обязательно за конечное время попадется первый или последний.

[maxal]

Юстас
Речь идет о гарантированном конечном времени (в худшем случае). Представьте, что на кубик для перемещения ему указывает вредная девочка Оля, которая хочет, чтобы Вася сортировал бесконечно долго. Сможет ли она добиться этой цели или же Вася рано или поздно все-таки отсортирует кубики, вопреки Олиному желанию?

[TOTAL]

Обозначим $h(i) =i-p(i)$ (от числа $i$ отняли занимаемую им позицию $p(i)$)
Если $h(i) = 0,$ то число $i$ стоит на подходящей позиции.

Приподнимем число $i$ с $h(i) > 0$ и перенесём его на свою позицию (сделав $h(i) = 0$). Если при этом переносе число $i$ пролетело над числами с неотрицательными $h,$ то величина $\sum_i|h(i)|$ не изменилась. А если пролетели хоть над одним отрицательным $h,$ сумма уменьшится. Однако (индукцией по длине участка с $h$ одного знака) нетрудно показать, что такие перелёты (не выходящие за участок одного знака и сохраняющие сумму $\sum_i|h(i)|$) не могут выполняться бесконечно. Сумма уменьшится. До нуля.

[Руст]

Если до перестановки i на свое место перестановка задавалась $p(j)$, то после операции перестановка задается через $p'(j)$, которое выражается так:
$p'(j)=p(j), j<min(i,p^{-1}(i)),j>max(i,p^{-1}(i)$
$p'(i)=i$,
$p'(j)=p(j+1),p^{-1}(i)\le j<i$ (p^{-1}(i)<i) $p'(j)=p(j-1),i<j\le p^{-1}(i)$.
Для функционала

$$S(p)=\sum_i|i-p(i)|$$

верно $S(p')\le S(p)$ но строгого неравенства может не быть. Строгое неравенство вроде имеет место для другого положительного целочисленного функционала

$$T(p)=\sum_i(p(i)-i)^2.$$

[TOTAL]

Руст писал(а):

Строгое неравенство вроде имеет место для другого положительного целочисленного функционала

$$T(p)=\sum_i(p(i)-i)^2.$$

Такой другой функционал может даже возрастать.
$3, 100, 101$ дает $2^2+98^2+98^2$
Перенесём тройку на свое место и получим
$100, 101, 3$ то есть $99^2+99^2+0^2$

[Dandan]

maxal писал(а):

Dandan писал(а):

Сумма \sum_i|i-p(i)| не увеличивается, а оставлять её такой же бесконечно мы не сможем, т.к. если эта сумма не меняется, то растёт количество инверсий.

Это неверно.
Например, в перестановке 42351 при перемещении 4 на свое место получается перестановка 23541 с тем же значением функции \sum_i|i-p(i)|, но меньшем числе инверсий.

ах да, нужно рассмотреть [инверсии - (количество чисел на своих местах)], кот. не уменьшается (при неизменности первого функционала). Если и этот не изменяется - то это только такие случаи, когда все сдвигаемые числа (кроме одного крайнего дальнего от дырки) стоят на своих местах (до сдвига). Типа вот этого (4)2351 -> 235(4)1. А дальше надо подумать ))

[maxal]

TOTAL в сообщении #189656 писал(а):

Приподнимем число $i$ с $h(i) > 0$ и перенесём его на свою позицию (сделав $h(i) = 0$). Если при этом переносе число $i$ пролетело над числами с неотрицательными $h,$ то величина $\sum_i|h(i)|$ не изменилась. А если пролетели хоть над одним отрицательным $h,$ сумма уменьшится. Однако (индукцией по длине участка с $h$ одного знака) нетрудно показать, что такие перелёты (не выходящие за участок одного знака и сохраняющие сумму $\sum_i|h(i)|$) не могут выполняться бесконечно. Сумма уменьшится. До нуля.

Это примерно то же, о чем говорил Dandan выше. Вы не учитываете возможность перелета над нулевыми значениями $h(i)$ - попробуйте "нетрудно" провести упомянутую индукцию...

Добавлено спустя 20 минут 13 секунд:

Dandan в сообщении #189740 писал(а):

Если и этот не изменяется - то это только такие случаи, когда все сдвигаемые числа (кроме одного крайнего дальнего от дырки) стоят на своих местах (до сдвига).

Может быть больше одного, причем не обязательно с краю от дырки:
783456912 -> 834569712

[Dandan]

maxal писал(а):

Может быть больше одного, причем не обязательно с краю от дырки:
783495612 -> 834956712

для этого примера первый фунционал уменьшается (для 7 изменение -6; для 8,9 изменение по +1; для 3,4 изменение по +1; а вот для 5,6 изменение по -1)

[maxal]

Dandan
Дык это описка в примере. Вот вам другой:
783456912 -> 834569712

[Dandan]

для него количество инверсий изменится на -2,
а количество чисел, стоящих на своих местах на -3

Добавлено спустя 27 минут 28 секунд:

В этих особых случаях (когда первый и второй функционал не меняются) еще важно то, что вот то крайнее число (6ка в примере (4)23615 -> 236(4)15) относительно вставляемого числа (4ки) находится в правильном порядке (4 левее 6 до сдвига). Дальше получается так :
Смотрим на 1. Если мы ее трогаем (или она уже на своем месте), то по замечанию ИСН задача сводится к случаю n-1. Если мы её сдвигаем каким-то из вот этих наших особых случаев, то поскольку она не была на своем месте, значит она была крайней из сдвигаемых чисел. Получается двигаться единица может только вправо, значит с некоторого места мы её вообще не будем двигать. Дальше смотрим на 2ку. По идее должно получаться аналогично. Ну и т.д.