☰

バブルソートの実装が永久にループするのはなぜですか? 質問する

tag-icon • tag-icon python algorithm sorting bubble-sort
バブルソートの実装が永久にループするのはなぜですか? 質問する

授業ではソートアルゴリズムをやっていますが、アルゴリズムについて話したり擬似コードを書いたりするときはよく理解できるのですが、実際のコードを書くときに問題があります。

これは Python での私の試みです:

mylist = [12, 5, 13, 8, 9, 65]

def bubble(badList):
    length = len(badList) - 1
    unsorted = True

    while unsorted:
        for element in range(0,length):
            unsorted = False
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                print badList
            else:
                unsorted = True

print bubble(mylist)

さて、これは（私が知る限り）正しくソートされますが、終了すると無期限にループします。

このコードを修正して、関数が適切に終了し、任意の（妥当な）サイズのリストを正しくソートするにはどうすればよいでしょうか。

PS 関数内に print は含めず、return を含める必要があることはわかっていますが、コードがまだ実際には動作していないため、まだそれを実行していません。

ベストアンサー1

スクリプトが現在動作しない理由を説明するために、変数の名前unsortedを に変更しますsorted。

最初は、リストはまだソートされていません。もちろん、sortedに設定しますFalse。

ループを開始するとすぐにwhile、リストはすでにソートされていると想定します。アイデアは次のとおりです。正しい順序になっていない2つの要素が見つかったらすぐに、sortedに戻りますFalse。sortedTrue 間違った順序の要素がない場合のみ。

sorted = False  # We haven't started sorting yet

while not sorted:
    sorted = True  # Assume the list is now sorted
    for element in range(0, length):
        if badList[element] > badList[element + 1]:
            sorted = False  # We found two elements in the wrong order
            hold = badList[element + 1]
            badList[element + 1] = badList[element]
            badList[element] = hold
    # We went through the whole list. At this point, if there were no elements
    # in the wrong order, sorted is still True. Otherwise, it's false, and the
    # while loop executes again.

コードの効率や可読性を高めるのに役立つ小さな問題もあります。

  • ループではfor、変数 を使用しますelement。技術的には、elementは要素ではなく、リストのインデックスを表す数値です。また、非常に長いです。このような場合は、「index」のように一時的な変数名を使用しますi。

    for i in range(0, length):

  • このrangeコマンドは、引数を 1 つだけ取ることもできます (引数はstop)。その場合、0 からその引数までのすべての整数のリストが返されます。

    for i in range(length):

  • のPython スタイルガイド変数名は小文字とアンダースコアで命名することを推奨します。これは、このような小さなスクリプトでは些細な問題です。むしろ、Python コードが最もよく似ているものに慣れるためのものです。

    def bubble(bad_list):

  • 2 つの変数の値を交換するには、タプル割り当てとして記述します。右側はタプルとして評価され ( とします(badList[i+1], badList[i])) (3, 5)、左側の 2 つの変数に割り当てられます ( (badList[i], badList[i+1]))。

    bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]

すべてをまとめると次のようになります。

my_list = [12, 5, 13, 8, 9, 65]

def bubble(bad_list):
    length = len(bad_list) - 1
    sorted = False

    while not sorted:
        sorted = True
        for i in range(length):
            if bad_list[i] > bad_list[i+1]:
                sorted = False
                bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]

bubble(my_list)
print my_list

(ちなみに、print ステートメントも削除しました。)

おすすめ記事