双方向バブルソートプルーフ

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 

私はメインループ条件で混乱少しです。アルゴリズムは左> =右の点に到達するか（の前に）どんなに次の二つのループで何が起こるか -

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