こんばんは。
Python user なら sort 使えば良いのですが、
考え方を味わいたかったので
まとめてみました٩(ˊᗜˋ*)و
取りあえず、以下の配列を小さい順に並べてみましょう。
x = [6,4,3,7,1,9,8]
っと言っても、いきなりヤレと言われてもハードルが高いので
まずは、一番小さい 1 を左端に移動させてみましょう。
例えばですが、2 つの値を比較し、小さいほうを左に移動させるアクションを
右端からやったら如何でしょうか？
例として x[5],x[6] を考えてみましょう。
# x[5] が x[6] より大きければ、、
if x[6] < x[5]:
# x[5] , x[6] の値を入れ替える
x[6],x[5] = x[5],x[6]
イメージはこんな感じです。
x[5], x[6] をブルーにハイライトしています。
次は x[4] VS x[5] で比較してみましょう。
x[4] < x[5] が成り立っています。
なので変更の必要はありません。
このように順番に比較していくと、
全体像は以下のようなイメージになります。
よかった、1 を左端に移動させることが出来ました!(^^)!
最終目標は小さい順に並べる事なので、他も並び替えが必要です。
ともあれ 1 が左端に寄せれたので、 1 は固定です!
誰が何と言おうと変えません(笑)!
取りあえず、固定の 1 は緑に変えました。
ここまでの流れを for 文で書いてみましょう。
#1.start は x[6],つまり n-1 です。
#2.end は x[1] vs x[0] なのでココでは、0 を入れておけば
# 実質は 1 までの代入となるので x[1] vs x[0] が実現します。
#3.数字は-1 ずつ減っていきます
#上記を並べると range(len(x)-1,0,-1) になります!
for j in range(len(x)-1,0,-1):
#例) x[6] < x[5] であれば入れ替えます!
if x[j] < x[j-1]:
x[j],x[j-1] = x[j-1],x[j]
多分問題ないと思います。
何か分かりにくかったら言ってください。m(_ _)m
では次です。
以下の図にあるように 1が最小であることが分かったら、
その次に小さい値を 1 の隣に持ってきましょう。
もう x[0] までデータを移動させる必要はありません。
x[6] から x[1] までで良いです。
ちょっとコードにしてみます。
# ↓ここを 0 から 1 に変えました。
for j in range(len(x)-1,1,-1):
#例) x[6] < x[5] であれば入れ替えます!
if x[j] < x[j-1]:
x[j],x[j-1] = x[j-1],x[j]
上記により x[6] から x[1] までを前述と同じように
比較作業を繰り返していきます。
結果は以下のようになります。
次は x[6] から x[2] です。
# ↓ここを 1 から 2 に変えました。
for j in range(len(x)-1,2,-1):
#例) x[6] < x[5] であれば入れ替えます!
if x[j] < x[j-1]:
x[j],x[j-1] = x[j-1],x[j]
もう良いですよね？(笑)
そうなんです、for 文のネストをすると
やりたいことが表現できます。
for i in range (len(x)-1):
for j in range(len(x)-1,i,-1):
if x[j] < x[j-1]:
x[j],x[j-1] = x[j-1],x[j]
全体像は以下のようになりました。
x = [6,4,3,7,1,9,8]
for i in range (len(x)-1):
for j in range(len(x)-1,i,-1):
if x[j] < x[j-1]:
x[j],x[j-1] = x[j-1],x[j]
print(x)
[1, 3, 4, 6, 7, 8, 9]
ソートは理解が楽しいんですけど、
説明に図が沢山いるので記事を書くのが疲れますね(笑)
本当は、もう変更の必要のない並びの場合は、
並び替えを切り上げたりする考え方もあるんでしょうけど、、ま、いっかな～
次はクイックソートかな。。
その後
2020/11/04 現在。やっぱり忘れてる(笑)
右端から小さい値を左端に移動させる作業を For で繰り返す。
ここは覚えてますが、
for の中身は何て書きますか？この辺を忘れます(笑)
困ったときは、配列長を 4 とかにして、
こじんまりな奴でサクッと書くと良い気がします。
右端に final 版の for のネストを書いていますけど、
前述の自分の記述と一致しますよね？