バブルソート:python実装と最適化

バブルソートの原理
1.隣接する要素を比較します.もし1番目が2番目より大きいなら、彼ら2人を交換します.そうでなければ、位置は変わりません.2.各ペアの隣接要素について、最初のペアから最後のペアまで同じ作業を行います.最後の要素は最大数になるはずです.3.最後の1つを除いて、すべての要素について上記の手順を繰り返します.4.比較する必要がなくなるまで、より少ない要素に対して上記の手順を繰り返します.
python実装
バブルソートの定義に基づいてpythonコードで実現できます

def bubble_sort(items):

    for i in range(len(items) - 1):  #i             （   n  ，     n-1     ）
        for j in range(len(items) - 1 - i): #j        ，        ，       ，                ，     i
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
        i += 1 #      
    print('   %d '% i)
    return items
    
arr = [1,2,8,4,7,5,6]
bubble_sort(arr)

実行結果は次のとおりです.

   6 
[1, 2, 4, 5, 6, 7, 8]

arr配列には7要素があり,6回のバブルソートを行い,ソート配列の導出に成功したことがわかる.これは最も一般的なバブルソートのアルゴリズム実装であり,理解に難くないはずであるが,この書き方には欠点がある:現在配列[6,1,2,3,4,5]があると仮定し,最初のバブルソート過程を行った後[1,2,3,4,5,6]になり,このとき配列はすでに秩序化されており,プログラムがこれ以上循環し続けると資源が浪費される.この問題を解決するために、いくつかの最適化方法を紹介します.
バブルソートの最適化方法1:
上記配列[6,1,2,3,4,5]は、1回目の配列後にすでに1つの秩序配列である[1,2,3,4,5,6].再配列を行うと、任意の2つの隣接要素間の位置がこれ以上変動しないことがわかり、配列が整っていることを意味する.この特性を利用して、私たちはプログラムの中で1面の“旗”を追加することができて、この“旗”はコンピュータに教えて、今隣接する要素はすべて位置を変動しないで、証明はすでに順序を並べました!、プログラムを終了できます!したがって、新しい変数を再指定し、初期値をFalseにし、位置変動が発生した場合はTrueにし、要素が位置を変換しなくなった場合は、すぐに初期値Falseにし、ループプログラムを終了することで、ソートサイクルの回数を減らすことができます.
最適化されたバブルソートアルゴリズムコードを見てみましょう.

def bubble_sort1(items):
    
    for i in range(len(items) - 1):
        flag = False   #    ‘  ’，            
        for j in range(len(items) - 1 - i):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                flag = True  #       ，    True，       ，    ；  ，      ，      ‘if not flag’  
        i += 1  
        if not flag:  #    ，     
            break
    print('   %d '% i)   
    return items

arr = [1,2,8,4,7,5,6]
bubble_sort1(arr)

実行結果は次のとおりです.

   3 
[1, 2, 4, 5, 6, 7, 8]

運転結果から、サイクル数が6回から3回になり、効率が倍増していることがわかりますよ.
バブルソート最適化方法2:
上記の書き方は効率が向上していますが、毎回左から右へ比較するので効率が悪く、双方向に並べ替えることができれば、一度左から右への並べ替え比較が終わったら、すぐに右から左へ並べ替え比較をします.このように効率はきっともっと高いです!これは、実際には、泡の並べ替えに基づいて改善された並べ替え方法:攪拌並べ替え/カクテル並べ替えを導入した.
再最適化されたコードを見てください.

def bubble_sort2(items):
    for i in range(len(items) - 1):
        flag = False
        for j in range(len(items) - 1 - i):
            if items[j] > items[j + 1]:
                items[j], items[j + 1] = items[j + 1], items[j]
                flag = True
        if flag:  #    
            flag = False
            for j in range(len(items) - 2 - i, 0, -1):  
                if items[j - 1] > items[j]:
                    items[j], items[j - 1] = items[j - 1], items[j]
                    flag = True
            i += 1
        if not flag:
            break
    print('   %d '% i) 
    return items

arr = [1,2,8,4,7,5,6]
bubble_sort2(arr)

実行結果を確認します.

   2 
[1, 2, 4, 5, 6, 7, 8]

やはり、運行効率がまた向上しました!サイクル数は前の3回から2回になった.
時間の複雑さ
1.ファイルの初期状態が正規であれば、1回のスキャンでソートが完了します.従って,発泡ソートの最適な時間複雑度はO(n)であった.2.初期ファイルが逆シーケンスの場合は、n-1回のソートが必要です.各ソートは、n−i回のキーワードの比較(1≦i≦n−1)を行い、比較のたびに交換記録位置に達するために記録を3回移動しなければならない.この場合,発泡配列の最悪時間複雑度はO(n 2)であった.
アルゴリズムあんていせい
バブルソートとは、小さな要素を前に調整したり、大きな要素を後ろに調整したりすることです.比較は隣接する2つの要素の比較であり、交換もこの2つの要素の間で発生する.だから、もし2つの要素が等しいならば、二度と交換しません;2つの等しい要素が隣接していない場合、前の2つの交換によって2つが隣接していても交換されないため、同じ要素の前後の順序は変わらないので、バブルソートは安定したソートアルゴリズムである.