sort を使わずにバブルソート

こんばんは。
Python user なら sort 使えば良いのですが、
考え方を味わいたかったので
まとめてみました٩(ˊᗜˋ*)و

取りあえず、以下の配列を小さい順に並べてみましょう。

```
x = [6,4,3,7,1,9,8]
```

っと言っても、いきなりヤレと言われてもハードルが高いので
まずは、一番小さい 1 を左端に移動させてみましょう。
例えばですが、2 つの値を比較し、小さいほうを左に移動させるアクションを
右端からやったら如何でしょうか？
例として x[5],x[6] を考えてみましょう。

```test.py
        # 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] をブルーにハイライトしています。
![図1.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/1cbe0f1e-00b3-061b-ddcd-90e2e6093ba3.png)
次は x[4] VS x[5] で比較してみましょう。
![図2.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/97f26fe4-cf80-ab04-6137-6aba8666c132.png)
x[4] < x[5] が成り立っています。
なので変更の必要はありません。

このように順番に比較していくと、
全体像は以下のようなイメージになります。
![図3.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/b1c55fdd-2d6d-fe97-4455-86227bc0f13f.png)
よかった、1 を左端に移動させることが出来ました!(^^)!
最終目標は小さい順に並べる事なので、他も並び替えが必要です。

ともあれ 1 が左端に寄せれたので、 1 は固定です!
誰が何と言おうと変えません(笑)!
取りあえず、固定の 1 は緑に変えました。
![図4.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/6670cf6f-1f8d-d990-6169-311ce58b5c7e.png)
ここまでの流れを for 文で書いてみましょう。

```test.py
#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 の隣に持ってきましょう。
![図4.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/6670cf6f-1f8d-d990-6169-311ce58b5c7e.png)
もう x[0] までデータを移動させる必要はありません。
x[6] から x[1] までで良いです。
ちょっとコードにしてみます。

```test.py
#                           ↓ここを 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] までを前述と同じように
比較作業を繰り返していきます。
結果は以下のようになります。
![図5.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/9295791f-e8de-e5f2-a59b-e511d9a1a57e.png)
次は x[6] から x[2] です。

```test.py
#                           ↓ここを 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 文のネストをすると
やりたいことが表現できます。

```test.py
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] 
```

全体像は以下のようになりました。

```bubble_test.py
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)
```

```実行結果.py
[1, 3, 4, 6, 7, 8, 9]
```

ソートは理解が楽しいんですけど、
説明に図が沢山いるので記事を書くのが疲れますね(笑)
本当は、もう変更の必要のない並びの場合は、
並び替えを切り上げたりする考え方もあるんでしょうけど、、ま、いっかな～
次はクイックソートかな。。

**その後**
2020/11/04 現在。やっぱり忘れてる(笑)
右端から小さい値を左端に移動させる作業を For で繰り返す。
ここは覚えてますが、
for の中身は何て書きますか？この辺を忘れます(笑)
困ったときは、配列長を 4 とかにして、
こじんまりな奴でサクッと書くと良い気がします。
![IMG_0037.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/225f70fb-98f4-bf35-c059-ba3193ecdd77.jpeg)
右端に final 版の for のネストを書いていますけど、
前述の自分の記述と一致しますよね？