这些用于冒泡排序的伪代码是如何工作的？

Question

我从维基百科得到了这段伪代码：

procedure bubbleSort( A : list of sortable items )
   n = length(A)
   repeat 
     swapped = false
     for i = 1 to n-1 inclusive do
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

这来自 a book（名为计算机科学原理）

BubbleSort( list )
    length  <-- lenght of list
    do  {
        swapped_pair    <-- false
        index       <-- 1
        while index <= length - 1 {
            if list[index] > list[index + 1] {
                swap( list[index], list[index + 1] )
                swapped_pair = true
                index <-- index + 1
            }
        }
    } while( swapped = true )
end

不知道哪个伪代码更好

我不明白的部分是 swapped_pair <-- false 部分和最后几行。

在第4行写swapped=false或swapped_pair <-- false.

为什么一开始就设置为false？如果不设置为 false 会发生什么？

最后几行，在维基百科上写道：

       end if
     end for
   until not swapped
end procedure

书中的伪代码是这样写的：

while( swapped = true )

最后几行是什么意思？

Answer 1

swapped 变量会跟踪最后一次遍历数组时是否进行了任何交换。

如果进行了交换，数组仍未排序，我们需要继续。
如果没有进行交换，则数组已经排序，我们可以到此为止。否则我们将进行冗余迭代。

这是我们为提高冒泡排序效率而进行的优化之一。如果您对更多优化感兴趣，可以在这里查看： http://www.c-programming-simple-steps.com/bubble-sort.html

然而，即使经过优化，冒泡排序的效率也太低而无法在实践中使用。在学习的同时，这是一个有趣的案例，但是如果您需要一个简单的排序算法，请改用插入排序。

这些用于冒泡排序的伪代码是如何工作的？

How these pseudocodes for bubble sort works?

pseudocode

bubble-sort