雙向氣泡排序證明

Question

我正在介紹算法課程。作爲家庭練習的一部分，我需要證明給定的雙向氣泡排序算法是正確的。 我們已經到下面的算法（用Python實現）：

def bidirectional_bubble_sort(a): 
left = -1 
right = len(a) 
while left < right: 
    swap = False 
    left += 1 
    right -= 1 
    for i in xrange(left, right): 
     if a[i] > a[i + 1]: 
      t = a[i] 
      a[i] = a[i + 1] 
      a[i + 1] = t 
      swap = True 
    if not swap: 
     return 
    else: 
     swap = False 
    for i in xrange(right - 1, left - 1, -1): 
     if a[i] > a[i + 1]: 
      t = a[i] 
      a[i] = a[i + 1] 
      a[i + 1] = t 
      swap = True 
    if not swap: 
     return 

我有點由主循環條件混淆。算法是否達到了left> = right（之前在內部返回語句之一退出）的位置？

Answer 1

while left < right: 
    swap = False 
    left += 1 
    right -= 1 

left和right被初始化爲數組的最左邊和最右邊，多數指數和每個迭代的向右和向左無條件的方向前進 - 無論發生在接下來的兩個循環的東西。所以顯然left >= right會發生並退出循環。

對於偶數長度的數組，left > right和奇數長度的數組，left == right將到達並退出循環。

調試，你會得到它自己。

編輯

我需要證明給定的雙向冒泡排序算法是正確的

你可以試試這個片斷。看起來上面的實現是不正確的。

def bidirectional_bubble_sort(a): 
    left = -1 
    right = len(a) 
    while left < right: 
     swap = False 
     left += 1 
     right -= 1 
     for i in xrange(left, right): 
      if a[i] > a[i + 1]: 
       t = a[i] 
       a[i] = a[i + 1] 
       a[i + 1] = t 
       swap = True 
     if not swap: 
      return 
     else: 
      swap = False 
     for i in xrange(right, left, -1): 
      if a[i] < a[i - 1]: 
       t = a[i] 
       a[i] = a[i - 1] 
       a[i - 1] = t 
       swap = True 
     if not swap: 
      return