ループを使わないソート

プログラミング

こんにちは。前回、ループを使わないでコピペプログラムを書いてみました。試しにやってみたのですが、案外プログラミング初心者は紙に挙動を書いてみたり、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できるんですけれどね・・・

ループを使わないと無駄に長くなりますね。それではまた。

Posted by 春日井 優