ループを使わないソート
こんにちは。前回、ループを使わないでコピペプログラムを書いてみました。試しにやってみたのですが、案外プログラミング初心者は紙に挙動を書いてみたり、print文で値を出力してみたりといったことをしていないので、意味があるのではないかと思い始めました。それならば、ソートのプログラムでループを使わないで書いて、その時の変数もわかるようにしたら、参考になるのでは？と思い、今回は試しにやってみたいと思います。
選択ソート
data = [3, 7, 5, 9, 0, 6, 1, 8, 2, 4]
# data[4] = 0 が、インデックス0以降で最小
mini = data[0:].index( min(data[0:]) ) + 0 # mini = 4
data[0], data[4] = data[4], data[0] # data = [0, 7, 5, 9, 3, 6, 1, 8, 2, 4]
# data[6] = 1 が、インデックス1以降で最小
mini = data[1:].index( min(data[1:]) ) + 1 # mini = 6
data[1], data[6] = data[6], data[1] # data = [0, 1, 5, 9, 3, 6, 7, 8, 2, 4]
# data[8] = 2 が、インデックス2以降で最小
mini = data[2:].index( min(data[2:]) ) + 2 # mini = 8
data[2], data[8] = data[8], data[2] # data = [0, 1, 2, 9, 3, 6, 7, 8, 5, 4]
# data[4] = 3 が、インデックス3以降で最小
mini = data[3:].index( min(data[3:]) ) + 3 # mini = 4
data[3], data[4] = data[4], data[3] # data = [0, 1, 2, 3, 9, 6, 7, 8, 5, 4]
# data[9] = 4 が、インデックス4以降で最小
mini = data[4:].index( min(data[4:]) ) + 4 # mini = 9
data[4], data[9] = data[9], data[4] # data = [0, 1, 2, 3, 4, 6, 7, 8, 5, 9]
# data[8] = 5 が、インデックス5以降で最小
mini = data[5:].index( min(data[5:]) ) + 5 # mini = 8
data[5], data[8] = data[8], data[5] # data = [0, 1, 2, 3, 4, 5, 7, 8, 6, 9]
# data[8] = 6 が、インデックス6以降で最小
mini = data[6:].index( min(data[6:]) ) + 6 # mini = 8
data[6], data[8] = data[8], data[6] # data = [0, 1, 2, 3, 4, 5, 6, 8, 7, 9]
# data[8] = 7 が、インデックス7以降で最小
mini = data[7:].index( min(data[7:]) ) + 7 # mini = 8
data[7], data[8] = data[8], data[7] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# data[8] = 8 が、インデックス8以降で最小
mini = data[8:].index( min(data[8:]) ) + 8 # mini = 8
data[8], data[8] = data[8], data[8] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print( data )
バブルソート
data = [3, 7, 5, 9, 0, 6, 1, 8, 2, 4]
# 1番目に小さい値 0 が浮かび上がってくる
if data[9] < data[8]: # data[9]=4 , data[8]=2
data[9], data[8] = data[8], data[9] # data = [3, 7, 5, 9, 0, 6, 1, 8, 2, 4]
if data[8] < data[7]: # data[8]=2 , data[7]=8
data[8], data[7] = data[7], data[8] # data = [3, 7, 5, 9, 0, 6, 1, 2, 8, 4]
if data[7] < data[6]: # data[7]=2 , data[6]=1
data[7], data[6] = data[6], data[7] # data = [3, 7, 5, 9, 0, 6, 1, 2, 8, 4]
if data[6] < data[5]: # data[6]=1 , data[5]=6
data[6], data[5] = data[5], data[6] # data = [3, 7, 5, 9, 0, 1, 6, 2, 8, 4]
if data[5] < data[4]: # data[5]=1 , data[4]=0
data[5], data[4] = data[4], data[5] # data = [3, 7, 5, 9, 0, 1, 6, 2, 8, 4]
if data[4] < data[3]: # data[4]=0 , data[3]=9
data[4], data[3] = data[3], data[4] # data = [3, 7, 5, 0, 9, 1, 6, 2, 8, 4]
if data[3] < data[2]: # data[3]=0 , data[2]=5
data[3], data[2] = data[2], data[3] # data = [3, 7, 0, 5, 9, 1, 6, 2, 8, 4]
if data[2] < data[1]: # data[2]=0 , data[1]=7
data[2], data[1] = data[1], data[2] # data = [3, 0, 7, 5, 9, 1, 6, 2, 8, 4]
if data[1] < data[0]: # data[1]=0 , data[0]=3
data[1], data[0] = data[0], data[1] # data = [0, 3, 7, 5, 9, 1, 6, 2, 8, 4]
# 2番目に小さい値 1 が浮かび上がってくる
if data[9] < data[8]: # data[9]=4 , data[8]=8
data[9], data[8] = data[8], data[9] # data = [0, 3, 7, 5, 9, 1, 6, 2, 4, 8]
if data[8] < data[7]: # data[8]=4 , data[7]=2
data[8], data[7] = data[7], data[8] # data = [0, 3, 7, 5, 9, 1, 6, 2, 4, 8]
if data[7] < data[6]: # data[7]=2 , data[6]=6
data[7], data[6] = data[6], data[7] # data = [0, 3, 7, 5, 9, 1, 2, 6, 4, 8]
if data[6] < data[5]: # data[6]=2 , data[5]=1
data[6], data[5] = data[5], data[6] # data = [0, 3, 7, 5, 9, 1, 2, 6, 4, 8]
if data[5] < data[4]: # data[5]=1 , data[4]=9
data[5], data[4] = data[4], data[5] # data = [0, 3, 7, 5, 1, 9, 2, 6, 4, 8]
if data[4] < data[3]: # data[4]=1 , data[3]=5
data[4], data[3] = data[3], data[4] # data = [0, 3, 7, 1, 5, 9, 2, 6, 4, 8]
if data[3] < data[2]: # data[3]=1 , data[2]=7
data[3], data[2] = data[2], data[3] # data = [0, 3, 1, 7, 5, 9, 2, 6, 4, 8]
if data[2] < data[1]: # data[2]=1 , data[1]=3
data[2], data[1] = data[1], data[2] # data = [0, 1, 3, 7, 5, 9, 2, 6, 4, 8]
# 3番目に小さい値 2 が浮かび上がってくる
if data[9] < data[8]: # data[9]=8 , data[8]=4
data[9], data[8] = data[8], data[9] # data = [0, 1, 3, 7, 5, 9, 2, 6, 4, 8]
if data[8] < data[7]: # data[8]=4 , data[7]=6
data[8], data[7] = data[7], data[8] # data = [0, 1, 3, 7, 5, 9, 2, 4, 6, 8]
if data[7] < data[6]: # data[7]=4 , data[6]=2
data[7], data[6] = data[6], data[7] # data = [0, 1, 3, 7, 5, 9, 2, 4, 6, 8]
if data[6] < data[5]: # data[6]=2 , data[5]=9
data[6], data[5] = data[5], data[6] # data = [0, 1, 3, 7, 5, 2, 9, 4, 6, 8]
if data[5] < data[4]: # data[5]=2 , data[4]=5
data[5], data[4] = data[4], data[5] # data = [0, 1, 3, 7, 2, 5, 9, 4, 6, 8]
if data[4] < data[3]: # data[4]=2 , data[3]=7
data[4], data[3] = data[3], data[4] # data = [0, 1, 3, 2, 7, 5, 9, 4, 6, 8]
if data[3] < data[2]: # data[3]=2 , data[2]=3
data[3], data[2] = data[2], data[3] # data = [0, 1, 2, 3, 7, 5, 9, 4, 6, 8]
# 4番目に小さい値 3 が浮かび上がってくる
if data[9] < data[8]: # data[9]=8 , data[8]=6
data[9], data[8] = data[8], data[9] # data = [0, 1, 2, 3, 7, 5, 9, 4, 6, 8]
if data[8] < data[7]: # data[8]=6 , data[7]=4
data[8], data[7] = data[7], data[8] # data = [0, 1, 2, 3, 7, 5, 9, 4, 6, 8]
if data[7] < data[6]: # data[7]=4 , data[6]=9
data[7], data[6] = data[6], data[7] # data = [0, 1, 2, 3, 7, 5, 4, 9, 6, 8]
if data[6] < data[5]: # data[6]=4 , data[5]=5
data[6], data[5] = data[5], data[6] # data = [0, 1, 2, 3, 7, 4, 5, 9, 6, 8]
if data[5] < data[4]: # data[5]=4 , data[4]=7
data[5], data[4] = data[4], data[5] # data = [0, 1, 2, 3, 4, 7, 5, 9, 6, 8]
if data[4] < data[3]: # data[4]=4 , data[3]=3
data[4], data[3] = data[3], data[4] # data = [0, 1, 2, 3, 4, 7, 5, 9, 6, 8]
# 5番目に小さい値 4 が浮かび上がってくる
if data[9] < data[8]: # data[9]=8 , data[8]=6
data[9], data[8] = data[8], data[9] # data = [0, 1, 2, 3, 4, 7, 5, 9, 6, 8]
if data[8] < data[7]: # data[8]=6 , data[7]=9
data[8], data[7] = data[7], data[8] # data = [0, 1, 2, 3, 4, 7, 5, 6, 9, 8]
if data[7] < data[6]: # data[7]=6 , data[6]=5
data[7], data[6] = data[6], data[7] # data = [0, 1, 2, 3, 4, 7, 5, 6, 9, 8]
if data[6] < data[5]: # data[6]=5 , data[5]=7
data[6], data[5] = data[5], data[6] # data = [0, 1, 2, 3, 4, 5, 7, 6, 9, 8]
if data[5] < data[4]: # data[5]=5 , data[4]=4
data[5], data[4] = data[4], data[5] # data = [0, 1, 2, 3, 4, 5, 7, 6, 9, 8]
# 6番目に小さい値 5 が浮かび上がってくる
if data[9] < data[8]: # data[9]=8 , data[8]=9
data[9], data[8] = data[8], data[9] # data = [0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
if data[8] < data[7]: # data[8]=8 , data[7]=6
data[8], data[7] = data[7], data[8] # data = [0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
if data[7] < data[6]: # data[7]=6 , data[6]=7
data[7], data[6] = data[6], data[7] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
if data[6] < data[5]: # data[6]=6 , data[5]=5
data[6], data[5] = data[5], data[6] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 7番目に小さい値 6 が浮かび上がってくる
if data[9] < data[8]: # data[9]=9 , data[8]=8
data[9], data[8] = data[8], data[9] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
if data[8] < data[7]: # data[8]=8 , data[7]=7
data[8], data[7] = data[7], data[8] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
if data[7] < data[6]: # data[7]=7 , data[6]=6
data[7], data[6] = data[6], data[7] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 8番目に小さい値 7 が浮かび上がってくる
if data[9] < data[8]: # data[9]=9 , data[8]=8
data[9], data[8] = data[8], data[9] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
if data[8] < data[7]: # data[8]=8 , data[7]=7
data[8], data[7] = data[7], data[8] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
# 9番目に小さい値 8 が浮かび上がってくる
if data[9] < data[8]: # data[9]=9 , data[8]=8
data[9], data[8] = data[8], data[9] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print( data )
挿入ソート
data = [3, 7, 5, 9, 0, 6, 1, 8, 2, 4]
# data[1] = 7 を挿入
if data[1] < data[0]: # data[1]=7 , data[0]=3
data[1], data[0] = data[0], data[1] # data = [3, 7, 5, 9, 0, 6, 1, 8, 2, 4]
# data[2] = 5 を挿入
if data[2] < data[1]: # data[2]=5 , data[1]=7
data[2], data[1] = data[1], data[2] # data = [3, 7, 5, 9, 0, 6, 1, 8, 2, 4]
if data[1] < data[0]: # data[1]=5 , data[0]=3
data[1], data[0] = data[0], data[1] # data = [3, 5, 7, 9, 0, 6, 1, 8, 2, 4]
# data[3] = 9 を挿入
if data[3] < data[2]: # data[3]=9 , data[2]=7
data[3], data[2] = data[2], data[3] # data = [3, 5, 7, 9, 0, 6, 1, 8, 2, 4]
if data[2] < data[1]: # data[2]=7 , data[1]=5
data[2], data[1] = data[1], data[2] # data = [3, 5, 7, 9, 0, 6, 1, 8, 2, 4]
if data[1] < data[0]: # data[1]=5 , data[0]=3
data[1], data[0] = data[0], data[1] # data = [3, 5, 7, 9, 0, 6, 1, 8, 2, 4]
# data[4] = 0 を挿入
if data[4] < data[3]: # data[4]=0 , data[3]=9
data[4], data[3] = data[3], data[4] # data = [3, 5, 7, 9, 0, 6, 1, 8, 2, 4]
if data[3] < data[2]: # data[3]=0 , data[2]=7
data[3], data[2] = data[2], data[3] # data = [3, 5, 7, 0, 9, 6, 1, 8, 2, 4]
if data[2] < data[1]: # data[2]=0 , data[1]=5
data[2], data[1] = data[1], data[2] # data = [3, 5, 0, 7, 9, 6, 1, 8, 2, 4]
if data[1] < data[0]: # data[1]=0 , data[0]=3
data[1], data[0] = data[0], data[1] # data = [3, 0, 5, 7, 9, 6, 1, 8, 2, 4]
# data[5] = 6 を挿入
if data[5] < data[4]: # data[5]=6 , data[4]=9
data[5], data[4] = data[4], data[5] # data = [0, 3, 5, 7, 9, 6, 1, 8, 2, 4]
if data[4] < data[3]: # data[4]=6 , data[3]=7
data[4], data[3] = data[3], data[4] # data = [0, 3, 5, 7, 6, 9, 1, 8, 2, 4]
if data[3] < data[2]: # data[3]=6 , data[2]=5
data[3], data[2] = data[2], data[3] # data = [0, 3, 5, 6, 7, 9, 1, 8, 2, 4]
if data[2] < data[1]: # data[2]=5 , data[1]=3
data[2], data[1] = data[1], data[2] # data = [0, 3, 5, 6, 7, 9, 1, 8, 2, 4]
if data[1] < data[0]: # data[1]=3 , data[0]=0
data[1], data[0] = data[0], data[1] # data = [0, 3, 5, 6, 7, 9, 1, 8, 2, 4]
# data[6] = 1 を挿入
if data[6] < data[5]: # data[6]=1 , data[5]=9
data[6], data[5] = data[5], data[6] # data = [0, 3, 5, 6, 7, 9, 1, 8, 2, 4]
if data[5] < data[4]: # data[5]=1 , data[4]=7
data[5], data[4] = data[4], data[5] # data = [0, 3, 5, 6, 7, 1, 9, 8, 2, 4]
if data[4] < data[3]: # data[4]=1 , data[3]=6
data[4], data[3] = data[3], data[4] # data = [0, 3, 5, 6, 1, 7, 9, 8, 2, 4]
if data[3] < data[2]: # data[3]=1 , data[2]=5
data[3], data[2] = data[2], data[3] # data = [0, 3, 5, 1, 6, 7, 9, 8, 2, 4]
if data[2] < data[1]: # data[2]=1 , data[1]=3
data[2], data[1] = data[1], data[2] # data = [0, 3, 1, 5, 6, 7, 9, 8, 2, 4]
if data[1] < data[0]: # data[1]=1 , data[0]=0
data[1], data[0] = data[0], data[1] # data = [0, 1, 3, 5, 6, 7, 9, 8, 2, 4]
# data[7] = 6 を挿入
if data[7] < data[6]: # data[7]=8 , data[6]=9
data[7], data[6] = data[6], data[7] # data = [0, 1, 3, 5, 6, 7, 9, 8, 2, 4]
if data[6] < data[5]: # data[6]=8 , data[5]=7
data[6], data[5] = data[5], data[6] # data = [0, 1, 3, 5, 6, 7, 8, 9, 2, 4]
if data[5] < data[4]: # data[5]=7 , data[4]=6
data[5], data[4] = data[4], data[5] # data = [0, 1, 3, 5, 6, 7, 8, 9, 2, 4]
if data[4] < data[3]: # data[4]=6 , data[3]=5
data[4], data[3] = data[3], data[4] # data = [0, 1, 3, 5, 6, 7, 8, 9, 2, 4]
if data[3] < data[2]: # data[3]=5 , data[2]=3
data[3], data[2] = data[2], data[3] # data = [0, 1, 3, 5, 6, 7, 8, 9, 2, 4]
if data[2] < data[1]: # data[2]=3 , data[1]=1
data[2], data[1] = data[1], data[2] # data = [0, 1, 3, 5, 6, 7, 8, 9, 2, 4]
if data[1] < data[0]: # data[1]=1 , data[0]=0
data[1], data[0] = data[0], data[1] # data = [0, 1, 3, 5, 6, 7, 8, 9, 2, 4]
# data[8] = 2 を挿入
if data[8] < data[7]: # data[8]=2 , data[7]=9
data[8], data[7] = data[7], data[8] # data = [0, 1, 3, 5, 6, 7, 8, 9, 2, 4]
if data[7] < data[6]: # data[7]=2 , data[6]=8
data[7], data[6] = data[6], data[7] # data = [0, 1, 3, 5, 6, 7, 8, 2, 9, 4]
if data[6] < data[5]: # data[6]=2 , data[5]=7
data[6], data[5] = data[5], data[6] # data = [0, 1, 3, 5, 6, 7, 2, 8, 9, 4]
if data[5] < data[4]: # data[5]=2 , data[4]=6
data[5], data[4] = data[4], data[5] # data = [0, 1, 3, 5, 6, 2, 7, 8, 9, 4]
if data[4] < data[3]: # data[4]=2 , data[3]=5
data[4], data[3] = data[3], data[4] # data = [0, 1, 3, 5, 2, 6, 7, 8, 9, 4]
if data[3] < data[2]: # data[3]=2 , data[2]=3
data[3], data[2] = data[2], data[3] # data = [0, 1, 3, 2, 5, 6, 7, 8, 9, 4]
if data[2] < data[1]: # data[2]=2 , data[1]=1
data[2], data[1] = data[1], data[2] # data = [0, 1, 2, 3, 5, 6, 7, 8, 9, 4]
if data[1] < data[0]: # data[1]=1 , data[0]=0
data[1], data[0] = data[0], data[1] # data = [0, 1, 2, 3, 5, 6, 7, 8, 9, 4]
# data[9] = 4 を挿入
if data[9] < data[8]: # data[9]=4 , data[8]=9
data[9], data[8] = data[8], data[9] # data = [0, 1, 2, 3, 5, 6, 7, 8, 9, 4]
if data[8] < data[7]: # data[8]=4 , data[7]=8
data[8], data[7] = data[7], data[8] # data = [0, 1, 2, 3, 5, 6, 7, 8, 4, 9]
if data[7] < data[6]: # data[7]=4 , data[6]=7
data[7], data[6] = data[6], data[7] # data = [0, 1, 2, 3, 5, 6, 7, 4, 8, 9]
if data[6] < data[5]: # data[6]=4 , data[5]=6
data[6], data[5] = data[5], data[6] # data = [0, 1, 2, 3, 5, 6, 4, 7, 8, 9]
if data[5] < data[4]: # data[5]=4 , data[4]=5
data[5], data[4] = data[4], data[5] # data = [0, 1, 2, 3, 5, 4, 6, 7, 8, 9]
if data[4] < data[3]: # data[4]=4 , data[3]=3
data[4], data[3] = data[3], data[4] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
if data[3] < data[2]: # data[3]=3 , data[2]=2
data[3], data[2] = data[2], data[3] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
if data[2] < data[1]: # data[2]=2 , data[1]=1
data[2], data[1] = data[1], data[2] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
if data[1] < data[0]: # data[1]=1 , data[0]=0
data[1], data[0] = data[0], data[1] # data = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print( data )
ループを使えば、明らかにスワップしなくてよいところでbreakできるんですけれどね・・・
ループを使わないと無駄に長くなりますね。それではまた。