Простенькая задачка на четность

[Rusit8800]

Задача придумана мной только что. Очень вероятно, что она не новая.

В ряд стоят несколько фишек. Разрешается менять местами любые две фишки, стоящие через одну. Доказать, что их можно переставить в обратном порядке тогда и только тогда, когда количество фишек нечетное.

[Dmitriy40]

Чтобы переставить фишки в обратном порядке первая должна попасть на последнее место. А она всегда прыгает лишь по нечётным числам (если нумерация позиций начинается с 1). Значит при чётном количестве фишек желаемая перестановка невозможна. Возможность перестановки при нечётном количестве фишек доказывается отдельно.

[svv]

Dmitriy40 в сообщении #1223394 писал(а):

Возможность перестановки при нечётном количестве фишек доказывается отдельно.

Вспомнив о сортировке методом пузырька, отправим на своё новое место сначала первую фишку, потом третью и т.д. Аналогично с чётными.

[Dmitriy40]

svv
Да это в общем очевидно, я думал про индукцию (переставляем первые две фишки, потом уменьшаем размер задачи на 2, повторяем, задача длины 3 решается тривиально), но это фактически тот же пузырёк. Собственно это оставил недоказанным специально, ведь спрашивалось в основном про чётное количество.

[Rusit8800]

Про пузырек я ничего не слышал, но свое доказательство для нечетного количества фишек я провел по индукции, так, как сказал Dmitriy40.

[Dmitriy40]

Про сортировку пузырьком. Это один из простейших методов сортировки массива чисел, известен давно, "проходится" кажется даже в школьном курсе информатики (правда без доказательств и математики). Один из самых неэффективных. Зато прост в понимании и реализации. Я бы сказал обязателен к изучению всем интересующимся программированием как один из базовых алгоритмов обработки данных.

[Rusit8800]

Dmitriy40 в сообщении #1223584 писал(а):

неэффективных

Во вычислительной сложности?

[svv]

Да. Элементарная операция очень проста (сравнить два соседних элемента и поменять их местами, если этого требует критерий сортировки), но этих операций, по современным меркам, требуется очень много: $\frac{N(N-1)}{2}$, независимо от начальной расстановки. Последнее очень досадно: даже если элементы уже стоят в правильном порядке, тупой метод всё равно сделает $\frac{N(N-1)}{2}$ сравнений, ничего не меняя после каждого сравнения.

[Dmitriy40]

svv в сообщении #1223598 писал(а):

Последнее очень досадно

Как раз нет, это легко обходится простыми эвристиками, незначительно усложняющими код для больших $N$. А для малых $N$ и эвристики не нужны, время работы и так мало (в абсолютном выражении).

(Замечания о пузырьке)

Rusit8800
Основная засада (неэффективность) в росте вычислительной сложности (времени работы) как $O(N^2)$, что для средних и больших $N$ многократно превышает другие более оптимальные методы (с сложностью $O(N \ln N)$). Обычно для массивов до тысяч элементов ещё можно применять, а для десятков тысяч и более - уже слишком медленно (по сравнению с другими более сложными методами). Для массивов в миллионы элементов разница во много раз будет видна невооруженным глазом (грубо - доли секунды или минуты работы), ну а сортировку миллиардного массива можно и несколько лет ждать против минуты для других методов. Базы данных же встречаются и заметно поболее размером.
Если мне будет позволено, приведу такую аналогию: возведение в натуральную степень можно делать последовательными умножениями или использовать логарифмы и получить ответ намного быстрее. Что не отменяет знания базовых вещей типа последовательных умножений (aka сортировка пузырьком).
Простите за ликбез.