Python 3：最適化されたバブルソート

Question

助けてください。バブルソートアルゴリズムを最適化する必要があります。これは、最適化されていないバブルソートよりも全体の比較を少なくするためです。私は「（唯一の左から右へ移動する）通常のバブルソート：

def bubbleSort(values): 
    n = len(values) - 1 
    swap = True 
    ncomp = 0 # My total comparisons counter 
    while swap: 
     swap = False 
     for i in range(n): # i = 0, 1, 2, ..., n-1 
      ncomp += 1 
      if values[i] > values[i+1]: 
       temp = values[i] 
       values[i] = values[i+1] 
       values[i+1] = temp 
       swap = True 
    return values, ncomp 

だから、基本的に私が作成する方法を知らない 『だけを作成するために管理両方向の旅を泡するbubbleSortPlus機能、最適化されたバブルソート』を：左から右へ、右から左への移動が直ちに続きます。理論的には、各パスでは、バブルの移動を短くする必要があります（変数内で最後のスワップの位置を保存し、その位置で次の移動を開始します）。

Answer 1

各繰り返しでリストを縮小しながら配列を前後にスキャンする方法を示すスケルトンコードです。

values = 100,101,102,103,104,105 

start = 0 
stop = len(values)-1 

while stop > start: 
    for i in range(start, stop): 
     print i, "compare", values[i], "with", values[i+1] 
    print "moved a large value to index", stop 
    print 

    stop = stop - 1 
    if stop == start: 
     break 

    for i in range(stop, start, -1): 
     print i, "compare", values[i], "with", values[i-1] 
    print "moved a small value to index", start 
    print 

    start = start + 1 

Answer 2

ナイーブなバブルソートにはswapフラグが含まれていないので、いずれの場合もO（n^2）の比較をすべて終了するまで戻りません。 swapフラグを指定すると、入力シーケンスが「ほぼソート」されている場合、比較の数はほぼ直線的になります。