Использование индукции для доказательства правильности сортировки пузырьков

Как мы можем показать, используя индукцию, что пузырьковая сортировка верна? Как мы выбираем инвариант, чтобы следовать на протяжении всей формулировки доказательства (этот шаг кажется мне произвольной задачей, поэтому, если его можно объяснить более глубоко, я был бы очень признателен)?

Я понимаю, что самые большие элементы всегда будут заканчиваться в конце списка после каждой итерации, но я не знаю, как использовать этот факт, чтобы показать, что алгоритм правильный.

Спасибо за помощь!

0

Решение

Я не уверен, что это то, что вы хотите, но его я так вижу.

Идея пузырьковой сортировки заключается в том, что вы идете через вектор значений (слева направо). Я называю это пропуском. Во время прохода пары значений проверяются и меняются местами в правильном порядке (справа вверху).

Во время первого прохода будет достигнуто максимальное значение. При достижении максимума будет выше, чем значение рядом с ним, поэтому они будут поменяться местами. Это означает, что Макс станет частью следующей пары в проходе. Это повторяется до тех пор, пока проход не будет завершен, и максимум останется в правом конце вектора.

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

При каждом следующем прохождении одно значение будет отсортировано справа.

Есть N значений и N проходов. Это означает, что после N проходов все N значений будут отсортированы

0

Другие решения

Других решений пока нет …