[解決済み] バブルソートの宿題

質問

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

これは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)

さて、これは（私が知る限り）正しくソートされますが、いったん終了すると、ただ無限にループするだけです。

どのようにこのコードを修正すれば、関数が正しく終了し、任意の（合理的な）サイズのリストを正しくソートできるようになりますか？

P.S. 私は、関数内で本当にプリントを持つべきではありませんし、私はリターンを持つべきですが、私のコードがまだ本当に動作しないので、私はまだそれをしませんでした知っています。

どのように解決するのですか？

今、あなたのスクリプトが動作していない理由を説明するために、変数 unsorted を sorted .

最初は、リストはまだソートされていません。もちろん sorted を False .

を開始すると同時に while ループを開始した時点で、リストはすでにソートされていると仮定します。このアイデアは、正しい順序でない 2 つの要素を見つけるとすぐに、その要素に対して sorted に戻します。 False . sorted は残ります True 間違った順序の要素がない場合のみ .

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 は要素ではなく、リストのインデックスを表す数値です。また、かなり長いです。このような場合は、単に一時的な変数名として i のように一時的な変数名を使用します。

  for i in range(0, length):
  
  

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

  for i in range(length):
  
  

• この 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文も削除しておきました)