エンジョイC028回目クイックソート２（2020-10-04）

ほえほえ＠スプシマン @hoehoe1234

エンジョイC28回目 2020/10/4（日） クイックソートではどうしてXとして中央の値を選ぶのか？の考察です。どうしてでしょうね？左端、右端の値を選んでも任意の値Xで動くのですからよさそうなものですが。 pic.twitter.com/LRgReYAllU

拡大

ほえほえ＠スプシマン @hoehoe1234

そうですね。もしほとんどが逆に整列済みであれば左端または右端を選ぶことにより２分割が１：その他になるかもしれません。整列済みの配列に要素を追加するような場合ですね。この場合の性能はn*nに近づき、かつ、再帰の深さが要素数に近くなってしまいます。

ほえほえ＠スプシマン @hoehoe1234

逆に中央値ですと、中央値Xにより１：その他に分割されるようなケースはあまり起きそうにありません。ですから中央を選んでおけばよいということになります（他にも中央値Xの選び方はありそうですね）。

ほえほえ＠スプシマン @hoehoe1234

４PのコードではPQに関して左右からループで検索した結果が(P>Q)であればブレークします。PQは入れ替える前はそれぞれ自身を含まないで左右は分類済みという意味の変数ですからP>Qであれば分類が終わっているのでbreakします。変数の意味は大切ですね。 pic.twitter.com/KQc70fOahs

拡大

ほえほえ＠スプシマン @hoehoe1234

さて、ではこれがどのような条件、データパターンの時に起きるでしょうか？これはなかなかの難問です。データのパターンとPQ変数の意味、Xを検索対象に含める意味の理解が必要です。このケースでは外側のdoループの１回めではこの定条件には当てはまりません。なぜなら値の範囲にXが必ず

ほえほえ＠スプシマン @hoehoe1234

含まれているからです（範囲からXを選びますので）。一度交換が起きた２度め以降のループでは、PとQの交換した要素がガードとなります。 G|今回の範囲|G P Q という状態ですね。「今回の範囲」の左右に、前回のループで交換した値がGとして存在することでループは必ず止まります。

ほえほえ＠スプシマン @hoehoe1234

ガード（G）は左はXかS、右はXかLとなりますのでそれぞれPとQは必ず止まります。この時にはP＞Qが成り立つのでPQがGで止まるということは今回の範囲は場合分け済み（すなわちすべてSかすべてLかのどちらか）となります。

ほえほえ＠スプシマン @hoehoe1234

昔のC言語なので大小比較とか位置関係をポインタ演算でやっていたりします。現代では通常、配列の要素を指すインデックスで比較します。 PQはポインタ n,m,kは要素数 i,j,kはインデックス（何番目） となることがおおいです。Kは両方に使われますね。 pic.twitter.com/2P20IefZyo

拡大

ほえほえ＠スプシマン @hoehoe1234

図上部は生徒さんがクイックソートのアルゴリズムを説明すうために作成してくれました。このように具体例をもって説明するのは大切ですね。具体例で検討したあとに裏にある考え方をたどっていくのが多くの場合にはよいです。

ほえほえ＠スプシマン @hoehoe1234

生徒さんが板書して説明中です。理解はできるけど説明が苦手、経験があまりない、職場で経験がつめない。というお話がおおいので積極的に説明の機会を設けるようにしています。 pic.twitter.com/CzYVBf0V5L

拡大

ほえほえ＠スプシマン @hoehoe1234

どう縮退していくのか？停止条件はなにか？縮退の最後のパターンにはどのようなものがあるか？などを丁寧に検証していきます。これは関数を記述する上でもっとも大切な技能の一つですね。モデル化・言語化して理解しないと漏れがでます。 pic.twitter.com/3QffqlJ7Jb

拡大

ほえほえ＠スプシマン @hoehoe1234

たとえばクイックソートでは範囲に関して、最初のループではXが含まれるので、２回目以降のループでは前回交換した値が左右にガードとしてあるというように言語化できれば、PQが範囲を超えることはない（１つとなりになることはある）というのが証明でき、漏れがないことがわかります。

ほえほえ＠スプシマン @hoehoe1234

停止条件はもう少し複雑ですが、２つの停止条件を詳細にパターン分けして検証後、言語化することで漏れがないことがわかります。このようにアルゴリズムは、最後に、ブロックごとに役割、データモデル、意味を言語化することによりやっと自分のものになるように思います。

ほえほえ＠スプシマン @hoehoe1234

もちろん、このようなことが最初からできるわけではなく、時間をかけて練習しながら検証していきます。ロジックを、リアリティをもって、データモデル（≒パターン）と変数の意味を添えて、自分の言葉で説明できるようになる。というのが目標です。 pic.twitter.com/2XRzPHp0Fi

拡大

ほえほえ＠スプシマン @hoehoe1234

関数は縮退して要素数が３以下になってからが勝負です。C言語ではオーバーランも利用するので（ポインタがオーバランしても要素にアクセスしなければ問題なし）さらにややこしくなります。 pic.twitter.com/u2QOb8KOqX

拡大

ほえほえ＠スプシマン @hoehoe1234

トップダウン解析の１つの例です。再帰を扱うときには、「再帰関数名＋変わるデータ」を一緒に記述します。この２つを合わせて「特化した関数」を呼び出すと理解してもいいですね。自分自身を呼び出しますが、付随するデータが違うので「別物」と考えるのも一つの方法です。 pic.twitter.com/L51KDGINai

拡大

ほえほえ＠スプシマン @hoehoe1234

ここから発展型です。左右を再帰で並び替えていたものを今度は左を再帰、右をループに書き換えます。この手法の詳細は白本を見ていただくとして、４つの変数要素（Left、Right、P、Q）を分割された右側範囲に対して再設定することで実現しています。 pic.twitter.com/cuPrNLwY1a

拡大

ほえほえ＠スプシマン @hoehoe1234

図にあるように全体範囲に対してL,R,P,Qを設定してループを開始しますが、全体を２つ（特例として３つ）に分割後は左を再帰に、右範囲に対してLRPQを正しく設定し直すことにより右半分に対してループ処理に置き換えられます。巧妙ですね。

ほえほえ＠スプシマン @hoehoe1234

直感ではすぐに正しく動くことは感じることができるとおもいますが、「どういう呼び出しになっているのか？」については検討が必要です。ループの中に再帰呼び出しが入っているのであらゆるところで再帰とループが繰り返されますので。

ほえほえ＠スプシマン @hoehoe1234

これに対しては、①ループ部分のみ理解②再帰部分のみ理解③組み合わせて理解という手順を踏むのがよいとおもいます。ループは「いまいるレベル」でずっと（約）半分ずつに範囲が縮退していきます。１ループ単位ごとに残りの半分は再帰にだします。 pic.twitter.com/8cU5NSXN6l

拡大

ほえほえ＠スプシマン @hoehoe1234

このような場合には「再帰を一旦忘れる」ということが必要になります。再帰は他の関数と考えて「ループがどのように機能するのか？」を考えます。同一レベルであれば常に右半分を要素として縮退していくような動きをします。１回目は全体を、２回目は右半分を、３回めはさらに残りの右半分をスキャン

ほえほえ＠スプシマン @hoehoe1234

スキャンするように動きます。次に再帰です。再帰は横にラインを引いて階層を分けると良いですね。図中央の２段めです。そのようにしたら次はさらに３段目となります。トップレベルの右半分に関しても次は２段めとして右半分の左半分が範囲として再帰呼び出しされます。

ほえほえ＠スプシマン @hoehoe1234

これで再帰の動きが把握できます。分けてー左再帰呼び出しー右はループ範囲として再設定となります。これで再帰の実行される順番も図上で表すことができます。最後に組み合わせです。１つのノードに注目すると「全体を分割－左を再帰ー右をループ範囲として分割」を繰り返しています。

ほえほえ＠スプシマン @hoehoe1234

図的にはわかりにくいですが、右側中央お２段めレイアにおいて、最初のループは黒の範囲、次のループは青の範囲、次のループは赤の範囲を全体に再設定してループします。そして各ループごとに左範囲は再帰にだします。１回目、２回目となるにつれて左再帰に出す範囲は半分になっていきます。 pic.twitter.com/LcCoJOrk6g

拡大

ほえほえ＠スプシマン @hoehoe1234

この図でいえば再帰の２段めには最初は大元の全体の半分の範囲で、次のループから（大元を基準とすると）１／４の範囲が、その次のループでは１／８の範囲が２段めの再帰として呼ばれます。ですから最初の左範囲の３段目と２回目ループの左範囲の２段めの要素数がだいたい同じになる仕組みです。