#【python】ソートプログラムを自分で作ってみる。（選択ソート、挿入ソート、バブルソート）
##選択ソート
最少値を見つけて先頭の要素と交換する。
実際の処理としては、複数の考え方を合わせる必要がある。
(1) 最少値を求める
(2) 最少値を先頭の値と入れ替える
(3) (1)と(2)を先頭が確定していない値の中で繰り返す
def min_init(arr, x):
min = x
for i in range(x, len(arr)):
if arr[min] > arr[i]:
arr[i], arr[min] = arr[min], arr[i]
def min_sort(arr):
for j in range(0, len(arr)-1):
min_init(arr, j)
print(arr)
a = [2,4,5,3,10,1,8,6]
min_sort(a)
#[1, 2, 3, 4, 5, 6, 8, 10]
###考え方
####(1) 最少値を求める
まずは最少値を求める式を考える。
minの初期値を0番目として、次の数値と比較する。
次の数値が小さい場合に、minを入れ替える
#最少値を求める
def min_val(arr):
min = 0
for i in range(1, len(arr)):
if arr[min] > arr[i]:
min = i
print(a[min])
#確認
a = [2,4,5,3,10,1,8,6,3,2]
min_val(a)
#1
####(2) 最少値を先頭の値と入れ替える
上記の最少値を求めるプログラムを応用して、最少値が見つかったタイミングで、その値と先頭の値を交換する。
最終的に、最少値が先頭にきた配列を求める。
#最少値を見つけて配列の先頭に移動する
def min_first(arr):
min = 0
for i in range(1, len(arr)):
if arr[min] > arr[i]:
arr[i], arr[min] = arr[min], arr[i]
print(a)
#確認
a = [2,4,5,3,10,1,8,6]
min_first(a)
#[1, 4, 5, 3, 10, 2, 8, 6]
####(3) (1)と(2)を先頭が確定していない値の中で繰り返す
上記を応用して処理を繰り返す。
注意点は、minの初期値を変数にする。こうすることで比較対象範囲がひとつづつ後ろにずれていく。
定数にしてしまうと、常に同じ値と比較することになり狙った出力にならない。
def min_init(arr, x):
min = x
for i in range(x, len(arr)):
if arr[min] > arr[i]:
arr[i], arr[min] = arr[min], arr[i]
def min_sort(arr):
for j in range(0, len(arr)-1):
min_init(arr, j)
print(arr)
#確認
a = [2,4,5,3,10,1,8,6]
min_sort(a)
#[1, 2, 3, 4, 5, 6, 8, 10]
##挿入ソート 先頭をソート済みとして、次の数値をどこに追加していくかを判断していく方法。
・未ソートの先頭の値とその前の値を比較
・未ソートの方が小さければ、未ソートがあった値を大きい値で上書きする。（未ソートの値は変数で保管しておく）
・未ソートの方が大きくなったところで確定する
def insert_sort(arr):
for i in range(1,len(arr)):
tmp = arr[i] #未ソートの先頭
j = i -1 #ソート済みの一番後ろ（未ソートの一個前）
#要素を比較して、tmpの方が小さければj+1の値を置き換えていく
while arr[j] > tmp and j >= 0:
arr[j+1] = arr[j]
j -= 1
#tmpの方が大きいなら、j+1をtmpで確定する
arr[j+1] = tmp
a = [2,4,5,3,10,1,8,6]
insert_sort(a)
print(a)
#[1, 2, 3, 4, 5, 6, 8, 10]
###tmpとは
変数。値が順次追加されたり、削除されたりしていく一時的な変数を明示するために使う。temporaryの略。
##バブルソート 後ろから、隣合う要素を比較して交換していく。
一番先頭の２つを比較し終わった時点で、先頭が確定する。
残りの要素で同じ操作を繰り返す。
処理の流れとしては、
(1) 最後の値を隣り合う値と比較して、より小さければ交換する。
(2) (1)の作業を繰り返す。先頭は1回づつ固定していく。
def bubble_sort(arrs):
for j in range(0, len(arrs)):
exchange(arrs, j)
def exchange(arr, j):
for i in range(len(arr)-1, j, -1):
if arr[i-1] > arr[i]:
arr[i-1], arr[i] = arr[i], arr[i-1]
#確認
a = [2,4,5,3,10,1,8,6]
bubble_sort(a)
print(a)
#[1, 2, 3, 4, 5, 6, 8, 10]
▼（参考）隣り合う値を比較し交換する
#小さい数値を前方に移動する
def exchange(arr):
for i in range(len(arr)-1, 0, -1):
if arr[i-1] > arr[i]:
arr[i-1], arr[i] = arr[i], arr[i-1]
print(arr)
#確認
a=[8,2,6,1]
exchange(a)
#[1, 8, 2, 6]