sort を使わずにクイックソート

こんばんは!(^^)!
昨日は、子供を寝かしつけようとして
そのまま自分も寝てしまいました(笑)。

では、クイックソートで小さい順に並べ替えてみましょう。
これまた面白い考え方でした。
今回は while を使います。復習を兼ねて簡単な奴を書いてみました。

```test.py
x = 10
pc = 5

# x > pc だったら、while の中に入って処理を実行
# !(x > pc) となったら、while 文は pass !
while x > pc:
    x -= 1
    print(x)

print("result is ",x)
```

ご覧の通り、x > pc である限り、while 文の中をグルグル回るのですが、
そのたびに x = x - 1 が実行されます。
その後、x = 6 になったら、一応 while 文の中に入れますが、
中の処理で x -= 1 となるので、x = 5 になるために、x > pc の関係が崩れるので、
次の処理では while 文を抜けざるを得ません。。
念のため、実行結果を載せます。

```実行結果.py
9
8
7
6
5
result is  5
```

以上から while 文のミソは、条件文に該当する限り、
処理を繰り返すことが出来る点です。

なんで、こんなの使うの？って話ですよね。
じゃあ、本題に入っていきましょう
(後で while が出てくるので覚えておいてください)。

今回はこちらの配列Xを使います。
![図1.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/9e7a891e-aa63-6080-833d-971f88ae3f64.png)
この配列の中央の値が何であっても、こいつを基準にソートをしていきたいと思います。
？？？何と比較するの？？？
はい、すいません。
一番左の値と、中央値を比較します。
![図2.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/7a1ecab8-8ff5-8fec-fd2c-a39e1c581260.png)
一応、1 vs. 5 明らかに中央値である 5 の方が大きいですね。
じゃあ、次です。
![図3.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/fbf0d6df-dcb2-72dd-9a53-94f17690b48a.png)
8 vs. 5 ! これは明らかに 8 の方が大きいですよね。
はい Stop !!。
First step の中央値より大きい値を見つける作業はここで終了です。
Second step は右端から中央値より**小さい**を見つける作業を行います。
じゃあ、端から行きましょう。
![図4.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/ffb1ec65-0d30-e935-b9d5-c7020c561676.png)
5 vs. 9 ! 
Stay で大丈夫ですね。次です!
![図5.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/68f535d3-c957-3374-7fb3-bb8924ac1331.png)
5 vs. 3 !
中央値の方が大きいですね。
OK です。見つけました。
Step 2 終了です。

次のステップは Step 1 と Step2 それぞれで見つけた値をひっくり返します。
※Step 1: 中央値より**大きい値**を見つける
※Step 2: 中央値より**小さい値**を見つける
イメージはこちらです。
![図6.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/53a617d7-9268-e4de-0d3a-347caaa05dd4.png)
変更後を赤字にしましたが、どうでしょうか？
それっぽく並び替え出来てますよね、大事です、雰囲気(笑)
では次に何をするのか？
Step 1,Step 2 を繰り返します。但し、Lptr +=1,Rptr -=1 とします。
そう、中央値に近づくようにして、同じことを繰り返していきます。
????なんで？
まぁ、まぁ、やってみましょうよ。

具体的には X[2] vs X[4]　と X[4] vs X[6] です。
![図7.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/6084a09a-6d4b-6851-a61e-404bc396d17a.png)
X[2] vs X[4] はビンゴですが、X[4] vs X[6] の場合は、 
X[4] < X[6] が成り立っているので、次の  X[4] vs X[**5**] を実行します。
![図8.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/e93b80dc-dc32-f741-6bed-80d18ac61b6a.png)
さぁ、交換の御時間です(笑)
![図9.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/afd1ac58-52c8-b241-bd00-1e03a2a1af2c.png)
以上で中央値 5 より左側の値は全て 5 未満、
中央値より右側は 5 より大きい配列が完成しました。

ここまでの動きをコードに落としてみましょう。
例えばですが、左側から中央値によって行く値を x[Lptr],
右側から中央値によって行く引数を x[Rptr] としてはどうでしょう。
※Lptr = Left pointer / Rptr = Right pointerセンス皆無(笑)!?

```test.py
#配列
x = [1,8,7,4,5,2,6,3,9]
#中央のポインタ
cen = len(x)//2

Lptr = 0
Rptr = len(x)-1

# x[Lptr] は中央値より小さい限り、ポインタ Lptr はインクリメント
while x[Lptr] < x[cen]:
    Lptr += 1
# x[Rptr] は中央値より大きい限り、ポインタ Rptr はディクリメント
while x[cen] < x[Rptr]:
    Rptr -= 1

#念のため、Lptr < Rptr であることをトリガにしておく
if Lptr < Rptr:
    #値をひっくり返す
    x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
```
実行してみましょう。

```
#実行前
#[1,8,7,4,5,2,6,3,9]

#実行後
 [1,3,7,4,5,2,6,8,9]
```

あれ? 3 と 8 がひっくり返っただけですね(笑)
そうか。

中央値より大きい/小さい値を探して
ひっくり返す作業を 1 回しか上記では表現出来ていませんね。
上記の記述を while Lptr < Rptr とすれば、この関係を維持する限り
前述の記述を繰り返してくれます(思い出して! 冒頭の while の説明!!)。

```test.py
x = [1,8,7,4,5,2,6,3,9]
cen = len(x)//2

Lptr = 0
Rptr = len(x)-1

#ポインタの位置 Lptr < Rptr の関係を維持している限り
#while 分の中身の処理を続けます。
while Lptr < Rptr:
    while x[Lptr] < x[cen]:Lptr += 1
    while x[cen]  < x[Rptr]:Rptr -= 1
 
    if Lptr < Rptr:
        x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
        #ひっくり返す作業が終了したら以下の作業をして
        #次の比較作業に入れるようにします。
        Lptr += 1
        Rptr -= 1
    
print(x)
```

実行結果は以下になります。

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

うん!(^^)!
中央値の 5 より左側は 5 未満
中央値の 5 より右側は 5 より大きい値に出来た( *´艸｀)
っで、どうします？次(笑)

まずは、前述の処理を行った後に
Lptr,Rptr は何処に辿り着いたんでしょうか。

```test.py
while Lptr < Rptr:
    while x[Lptr] < x[cen]:Lptr += 1
    while x[cen]  < x[Rptr]:Rptr -= 1
```

Lptr = 3 の時に Lptr += 1 なので、Lptr = 4
Rptr = 5 の時に Rptr -= 1 なので、Rptr = 4
Lptr = Rptr = 4 となり、while 文の条件であった Lptr < Rptr が
これで崩れますので、while 文を抜けます。
念のため、実行してみましょう。

```
[1, 3, 2, 4, 5, 7, 6, 8, 9] Lptr = 4  Rptr = 4
```

なるほど。とりあえず、図にしてみましょう。
![図10.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/dc1db837-4487-2924-63db-02d3301622ff.png)
以下のように追加で少しイジルとどうでしょうか。

```test.py
x = [1,8,7,4,5,2,6,3,9]
cen = len(x)//2

Lptr = 0
Rptr = len(x)-1

           #↓ "=" を追加!!
while Lptr <= Rptr: #　Lptr == Rptr でも while 内の処理に入る
    #以下の while はスキップします。
    #<===ここから
    while x[Lptr] < x[cen]:Lptr += 1
    while x[cen]  < x[Rptr]:Rptr -= 1
    #<== ここまで

#　Lptr == Rptr でも while 内の処理に入る
            #↓ "=" を追加!!
    if Lptr <= Rptr:
        #x[4],x[4] = x[4],x[4] なので無害
        x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
        #ここが重要!!それぞれインクリメント、ディクリメント!
        Lptr += 1
        Rptr -= 1
    
print(x,f"Lptr = {Lptr}",f" Rptr = {Rptr}")
```

一部に "=" を追加しました。
これにより実行結果は以下のようになります。

```実行結果.py
[1, 3, 2, 4, 5, 7, 6, 8, 9] Lptr = 5  Rptr = 3
```

なんと、Lptr と Rptr の位置が逆転しました。
![図11.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/87dca762-9c39-b737-8afa-edd43b3c2763.png)
ではでは、この状態で与えられた配列 x を、
領域1: x[0] ~ Rptr(=x[3]) 
領域2: Lptr(=x[5])　~ x[8]
っと分けて、それぞれに今までと同じ処理を行ったら、どうなりますか？
そうです、再帰です。
なんか生まれそうですよね!?(笑)
再帰を使いやすくするために記述を変えておきます。

```test.py
#left :初期値としては一番左
#right:初期値としては一番右 
def quick_sort(x,left,right):
    
    Lptr = left
    Rptr = right
    cen  = (left+right)//2
    
    while Lptr <= Rptr:
        while x[Lptr] < x[cen]:Lptr += 1
        while x[cen] < x[Rptr]:Rptr -= 1
        if Lptr <= Rptr:
            x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
            Lptr += 1
            Rptr -= 1
    print(x,f"Lptr = {Lptr}",f" Rptr = {Rptr}")
    
if __name__ =="__main__":
    x = [1,8,7,4,5,2,6,3,9]
#使用する配列 x
#left の初期値は左端なので 0 を入力
#right の初期値は右端なので len(x)-1 を入力
    quick_sort(x,0,len(x)-1)
```

これから再帰のイメージは以下の通りです。
![図12.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/27b6d642-b408-a4e5-47d2-f193971936ef.png)
left , Rptr を left , right とした領域(緑)、
Lptr , right を left , right とした領域(青)なんか動きそうですね。
こんな記述は如何でしょうか。

```quick_sort.py
def quick_sort(x,left,right):
    
    Lptr = left
    Rptr = right
    cen  = (left+right)//2
    
    while Lptr <= Rptr:
        while x[Lptr] < x[cen]:Lptr += 1
        while x[cen] < x[Rptr]:Rptr -= 1
        if Lptr <= Rptr:
            x[Lptr],x[Rptr] = x[Rptr],x[Lptr]
            Lptr += 1
            Rptr -= 1
    print(x,f"Lptr = {Lptr}",f" Rptr = {Rptr}")
    #前述の図にあるように left < Rptr の関係が成り立てば
    #左領域を再帰でソート
    if left < Rptr:
        quick_sort(x,left,Rptr)
    #前述の図にあるように Lptr < right の関係が成り立てば
    #右領域を再帰でソート
    if Lptr < right:
        quick_sort(x,Lptr,right)
    
if __name__ =="__main__":
    x = [1,8,7,4,5,2,6,3,9]
    quick_sort(x,0,len(x)-1)
```

実行結果はこちらです。

```
[1, 3, 2, 4, 5, 7, 6, 8, 9] Lptr = 5  Rptr = 3
[1, 2, 3, 4, 5, 7, 6, 8, 9] Lptr = 2  Rptr = 1
[1, 2, 3, 4, 5, 7, 6, 8, 9] Lptr = 1  Rptr = -1
[1, 2, 3, 4, 5, 7, 6, 8, 9] Lptr = 3  Rptr = 1
[1, 2, 3, 4, 5, 6, 7, 8, 9] Lptr = 6  Rptr = 5
[1, 2, 3, 4, 5, 6, 7, 8, 9] Lptr = 8  Rptr = 6
```

最後の行を見ると、ソートされていますね。
途中経過の解説はどうしよう、やったほうが良いかな(;´･ω･)

**その後**
2020/11/05 丸っきり忘れたので、
今更自分の記事を読み返しました。
なるほど、分かり易い(笑)

ただ、書いた本人が今になって、まるっきり忘れているので、
内容が軽いんだと思います(*´з`)

とりあえず、読み直して自分の中にイメージを作りました。
例のごとく、ホワイトボードに向かいましたが、下の図にある { までは何とか。。
①、② のような再帰処理が出来ませんでした。
![IMG_0040.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/466a58cc-3cc9-9a45-fd4b-447019995e87.jpeg)
図にも書きましたが、センターを超えた後に分割したい領域の両端が、
left < rptr, lptr < right であることをさえわかれば
if 文で条件を定義してあげることで再帰処理に導けます。
確かに、再帰処理はそんなことしてましたよ(笑)。

あと昔の自分の記事は main() に並び替え後の値を返していたわけでは無いので、
そこがイマイチのような気がしました。
そのため上図にあるように return nums として、
最終的には main() に値を返すようにしました。

```quick_sort.py
def quick_sort(left,right,nums):
    Cptr = (left+right)//2
    Rptr = right
    Lptr = left
    
    while Lptr <= Rptr:
        while nums[Lptr] < nums[Cptr]:Lptr += 1
        while nums[Cptr] < nums[Rptr]:Rptr -= 1
        if Lptr <= Rptr:
            nums[Lptr],nums[Rptr] = nums[Rptr],nums[Lptr]
            Lptr += 1
            Rptr -= 1
    
    if left < Rptr:
        quick_sort(left,Rptr,nums)
    if Lptr < right:
        quick_sort(Lptr,right,nums)    
        
    return nums

if __name__ == "__main__":
    
    nums = [1,8,7,4,5,2,6,3,9]
    print(quick_sort(0,len(nums)-1,nums))
```

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