Python初心者がバブルソートを整理する


これは備忘録です 

忘れることないと思うけど

(追記 2020/0611:13:00)
@shiracamusさんからアドバイスを受けましたので修正します。

バブルソートって

バブルソートとは、基本交換法とも呼ばれるソートアルゴリズムで、大体適当に作ろうとするとこれになる

中身の解説

bubble.py
'''1'''def bubble(T):
'''2'''    i = len(T)-1
'''3'''    while i:
'''4'''        for j in range(i-1):
'''5'''            if T[j] > T[i]:
'''6'''                T[j],T[i] = T[i],T[j]
'''7'''        i -= 1
'''8'''    return T

うわー、とっても短いアルゴリズムだー

と、書いた側も少しビックリ。
これだけ短いので行番号入れて解説してみる。

  1. 関数宣言、引数は数字配列型で作成したT。
  2. 注意点len(T)で返ってくる数字は「長さ」なので、配列番号にそのまま挿入すると配列外を参照するエラーになる。
  3. while文にはifと同じくtrueとなる文字が入ればいいのでi!=0と同じ意味になるi単体を入れてみた。
    • forがどうしても使いたいのであれば1行目を消してfor i in range(len(T)-1,0,-1):と書けばイける。
  4. ここはforで。range(i)でもいいっちゃいいが、ループが一回無駄になります。
    • T[i]>T[i] 同じもの比べればfalseやろ
  5. 配列の右側が大きくなってほしいので、左が大きければスワップします。
  6. スワップ。1行で済ませるサボリ魔の鑑1行でまとめられるからきれい。
  7. バブルソートでは後ろから結果が確定していくので-1する。Pythonで一番気に入らないことはマイマイできないことです。
  8. Tを返す。ループが中にあって返す形があると再起関数にしたくなってくる変人なのであとで遊んできます。

バブルソートは実は重い

Wikiを参考にしてもらうとわかるけれども、ソートするにあたって二重ループになっているアルゴリズムなので重いというのが特徴
また、いちいちすべてをスワップするのも重くなる原因なので、改善アルゴリズムではデータを退避させたりする形にしたりします。

bubble2.py
def bubble2(T):
    for i in range(len(T)-1,0,-1):
        tmp = T[0]
        for j in range(1,i+1):
            if tmp < T[j]:
                tmp , T[j] = T[j], tmp
            T[j-1]=T[j]
        T[i] = tmp
        print(T)
    return T

一応その場のノリで作ってみたけどコレもまだ改善点あるかな?あるはず。

余談

ランダムで数字の重複のない配列を作成するプログラムを組んだので例示しておきます。

(修正部分)

デフォルト引数にリストを使うのは避けましょう。
参考: https://docs.python.org/ja/3/faq/programming.html#why-are-default-values-shared-between-objects

xMake(i , T=[-1])としていた部分とそれによるプログラムの本文を修正させていただきました。

makeLis.py
import random as r
def xMake(i,T = None ):

    if T is None:
        T = [r.randint(1,i)]*i
        return xMake( 1 , T )
    if i == len(T):
        return T

    T[i] = r.randint(1,len(T))
    for j in range(i):
        if T[i] == T[j]:
            return xMake( i , T )
    return xMake( i+1 , T )


print(xMake(10))
>>[2, 1, 3, 6, 4, 10, 9, 5, 7, 8]
print(xMake(20))
>>[13, 20, 1, 12, 7, 8, 6, 4, 17, 11, 14, 9, 18, 3, 5, 10, 15, 2, 19, 16]

意地でも再起関数を使う民 もっといい書き方やスッキリした書き方があれば教えてください。

@shiracamusさんから教えていただきました。

rangeとsampleを使うとスッキリ書けます。

By_shiracamus.py
import random as r

def xMake(i):
    return r.sample(range(1, i + 1), k=i)

print(xMake(10))
print(xMake(20))

random.sampleを使うとこんなにも楽になるのですね……!
ありがとうございます!参考にさせていただきます!

関数の宣言する際に自分はx〇〇()と名前を付けることが多いです(大体が番号)。
目的無くプログラムを書いたりコピーして書き方を変えたりするのと、関数名に法則がないとプログラムするときに書き間違えたりするので。
そして、実際に使うことになったときにテキストエディタの置換機能で書き換えてわかる名前にする、ということをします。
コレがいいことなのかはわかりませんが、元々英語が苦手なのでスペルミスをする等の恥ずかしいことを時々するので。