使用感應來證明冒泡排序是正確的

Question

我們如何使用感應表明冒泡排序是正確的？我們如何選擇在整個證明的制定過程中遵循的不變量（這一步對我來說似乎是一個任意的任務，所以如果可以更深入地解釋，我將不勝感激）？

我知道每次迭代後最大的元素總是會在列表的末尾結束，但我不知道如何使用這個事實來證明算法是正確的。

感謝您的幫助！

Answer 1

我不確定這是你想要的，但他是我如何看待它。

氣泡排序背後的想法是，你去通過值的向量（從左到右）。我稱這爲通過。在傳遞過程中，對值進行檢查並交換爲正確的順序（右上角）。

在第一次過程中，將達到最大值。當達到最大值時會比它旁邊的值更高，因此它們將被交換。這意味着max將成爲下一對的一部分。這一直重複直到通過完成，並且max被留在向量的右端。

在第二次通過期間，向量中的第二高值也是如此。唯一的區別是它不會在最後與最大值交換。現在正確設置了兩個最正確的值。

我每下一個傳球一個值就會被整理到右邊。

有N個值和N遍。這意味着在N次通過後，所有N值都將被排序。