Open10
VisuAlgo(アルゴリズムのサイト）を見てPythonでアルゴリズムをかく
i_reiVisuAlgoのアルゴリズムを、Pythonで再現していく。
手順としては、
- VisuAlgoでアルゴリズムを見て理解
- Pythonで再現する
Pythonの練習とアルゴリズムの習得のため。VisuAlgoに表示されるコードは読んでいない（読めない）。
コードの間違い、コードをこう改良したらいいなど意見があったら教えてください。
再現できたかどうかの確認はリストを要所で出力して確認しています。
i_reiランダムなリストの作成は以下で行う。
import random
n = int(input())
a = [random.randint(1, 100) for i in range(n)]
バブルソート
bubble_sort.py
import random
n = int(input())
a = [random.randint(1, 100) for i in range(n)]
complete = False
while(not complete):
ok = False
for i in range(len(a) - 1):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
ok = True
if not ok:
complete = True
completeはバブルソートが終了しているかいないかの確認、okは全てソートできているかの確認用（紛らわしいし改良できると思う）
i_rei選択ソート
selection_sort.py
import random
n = int(input())
a = [random.randint(1, 100) for i in range(n)]
i = len(a) - 1
while i:
# 並べ替えが完了した部分を示す
f = len(a) - 1 - i
# 最小の数のリストインデックス
key = f
for j in range(f, len(a)):
if a[key] >= a[j]:
key = j
if a[key] < a[f]:
a[key], a[f] = a[f], a[key]
i -= 1
挿入ソートに苦戦。
今考えているのは、取り出した値を、他の値との差の絶対値を計算することで一番近い値を導き出し、それとの差を計算して前後に挿入することでソートしようという案。
i_rei挿入ソート
insertion_sort.py
import random
n = int(input())
a = [random.randint(1, 100) for i in range(n)]
print(a)
for i in range(len(a) - 1):
b = []
# print(i)
key = i + 1
for j in a[:key]:
if not j == a[key]:
b.append(abs(a[key] - j))
if a[key] < a[b.index(min(b))]:
a.insert(b.index(min(b)), a[key])
del a[key + 1]
elif a[key] >= a[b.index(min(b))]:
a.insert(b.index(min(b)) + 1, a[key])
del a[key + 1]
print(a)
読みにくい。いいコードじゃない。
一応これでソートできるが、ソートするリストに同じ値のものがあると正しくソートできない。ただ、半分完成ということで、次に進む。
i_reiマージソートに挑戦中。
上手くプログラムに表せない。やっていることはわかるけれど...プログラムに落とし込めないということは、どこかに理解していない部分があるのか。
i_reiマージソートを作っている。少し手順が違うかもしれないけれど、
- 二つずつに分割
- 分割したものを二つくっつけてソートし、四つずつにする
- それをくっつけて必要なら分割。全体が一つの数列に結合するまで繰り返す
というのをすればできるのではないかと思っている。
i_reiマージソートができない、ギブアップ。分からない問題を深く考え続けることと、ある程度考えても分からないものはそれ以上考えても分からないからを諦めること、どちらがいいのだろう？
i_reiあとこれ以後、ソートの数列の長さは10に固定。