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'''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
うわー、とっても短いアルゴリズムだー
と、書いた側も少しビックリ。
これだけ短いので行番号入れて解説してみる。
- 関数宣言、引数は数字配列型で作成したT。
-
注意点
len(T)
で返ってくる数字は「長さ」なので、配列番号にそのまま挿入すると配列外を参照するエラーになる。 -
while
文にはif
と同じくtrue
となる文字が入ればいいのでi!=0
と同じ意味になるi
単体を入れてみた。-
for
がどうしても使いたいのであれば1行目を消してfor i in range(len(T)-1,0,-1):
と書けばイける。
-
- ここは
for
で。range(i)
でもいいっちゃいいが、ループが一回無駄になります。- T[i]>T[i] 同じもの比べれば
false
やろ
- T[i]>T[i] 同じもの比べれば
- 配列の右側が大きくなってほしいので、左が大きければスワップします。
- スワップ。
1行で済ませるサボリ魔の鑑1行でまとめられるからきれい。 - バブルソートでは後ろから結果が確定していくので-1する。Pythonで一番気に入らないことはマイマイできないことです。
- Tを返す。ループが中にあって返す形があると再起関数にしたくなってくる変人なのであとで遊んできます。
バブルソートは実は重い
Wikiを参考にしてもらうとわかるけれども、ソートするにあたって二重ループになっているアルゴリズムなので重いというのが特徴
また、いちいちすべてをスワップするのも重くなる原因なので、改善アルゴリズムではデータを退避させたりする形にしたりします。
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])としていた部分とそれによるプログラムの本文を修正させていただきました。
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を使うとスッキリ書けます。
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〇〇()
と名前を付けることが多いです(大体が番号)。
目的無くプログラムを書いたりコピーして書き方を変えたりするのと、関数名に法則がないとプログラムするときに書き間違えたりするので。
そして、実際に使うことになったときにテキストエディタの置換機能で書き換えてわかる名前にする、ということをします。
コレがいいことなのかはわかりませんが、元々英語が苦手なのでスペルミスをする等の恥ずかしいことを時々するので。
Author And Source
この問題について(Python初心者がバブルソートを整理する), 我々は、より多くの情報をここで見つけました https://qiita.com/sola_wing529/items/a091a4db860779b5c032著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .