エンジョイC029回目クイックソート３（2020-10-11）

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

エンジョイC　29回目 （日） 引き続きクイックソートの分析です。コードの詳細な解析はできたので今度はロジックの言語化をします。ロジックは大きく分けて①検索パート②判定パートA③交換パート④判定パートB（とPQを１つすすめる）です。 pic.twitter.com/GYMPgLvCm7

拡大

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

この分析では判定パートAとBでどのような条件の場合にブレークするか、また、そのブレークはどのようなデータ状態を意味するか？を言語化していきます。この言語化はなかなかむずかしいですね。 pic.twitter.com/sfFmigsATU

拡大

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

ループの１回目では判定Aでは絶対にBreakしません。Break条件はP>QとなっておりPQが交差した条件で発生します。ループの１回めは要素の中から中央値Xを選択しますのですでにPとQは最大限進んでも一回目のループでは同一のノードを指し、交差は発生しません。ではどういう場合にbreakするのでしょうか？

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

要素交換前においてはPとQのそれぞれPQの位置を含まない左側と右側は分類済みです。これが検索パートで交差しているということは１）Pが右側のガードまで突き抜けた、２）Qが左側のガードまで突き抜けた、３）PとQが要素中で交差したの３つの場合が考えられます。

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

１）はPQの間の要素がすべてSmallであった場合に発生します。２）のはPQの間の要素がすべてLargeであった場合に発生します。３）はSS・・・LLのように要素がXを含まない状態ですでに分類されている状態で発生します。 pic.twitter.com/wsmKxanwqJ

拡大

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

これは言い換えると、ループの２回目以降に要素がXを含まないでSのみ、LのみまたはSとLが左右に分類済み、すなわち「すでに分類済み」の状態である場合に発生します。すでに分類済みなのでPとQが定義どりに交差するということですね。 pic.twitter.com/JiatYx1PTD

拡大

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

これで判定Aでのbreak条件は整理して言語化できました。要素を交換する前はPQのそれぞれ左右が分類済みであるのでPQの間がすでに分類済みの状態であればPとQは交差するということになります。 pic.twitter.com/hgqrpntPku

拡大

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

上記図の左側は判定Bの条件について生徒さんが分析してくれた式です。判定BではやはりPがQを超えるまでループをします（while(++p <= --q)）。ここで注意するのはこの時点（③の交換後）ではすでにPQを含めて分類済みなので比較はそれぞれのポイントを一つづつ進めた値で比較します。

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

もし進めた値が交差すれば（P>Q)、それは進める前のPとQの位置ですでに左右で分類済みであり進めた値からみるとPQの位置を含まない左右が分類済みでありこの状態は判定Aと同じ状態となります。生徒さんは次のような分析をされました。

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

１）判定AのあとのPQの位置はP<=Qである（そうでなければbeakしているので） ２）判定BはPQが交差するためにはポインタを進める前に 　ａ）PとQが同じであったか 　ｂ）PとQが隣り合っていたか のどちらかの状態で有ることが必要となります。

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

３）ａ）のケースでは検索パートで検索した結果、PQが同じ位置で停止している、すなわち検索された要素はXであるということになります。 ４）ｂ）のケースでは検索した結果、要素が２つに縮退した状態となります（左はXかL、右はXかS）。

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

まとめると、判定Bで条件が成立するのは検索した結果PQが同じ位置で停止した（要素はX）または、左右に隣り合う位置で停止した状態の場合にbreakします。 ａ）の場合はPQが１つづつすすので真ん中の要素を除いた３つに配列が３分割されます。ｂ）の場合は判定Aと同じく左右に分割されます。ここでも

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

PQを進めたあとはPQを含まないで左右は分割済みであるということです。ａ）のケースは 　　　S X L ↑　↑ Q P となりますがそれでも依然、Pからみて左とQからみて右は分類済みです。ただし次の再帰呼び出しではXは双方含めないことになります。

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

これでクイックソートの分析は完了しました。たった２０行程度のコードですがこれほどの解析をしないと実際にどう動くのか？終了条件は正しいのか？はわからず、自分のモノにはなりません。やはりCSは時間がかかりますね。でも楽しいです。

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

次に文字列を対象にクイックソートを実行します。そのまえにまずC言語の文字列はどのようなものであるかの復習です。アルゴリズムの演習なので１バイトのアスキーコードのみを対象として検討します。文字（文字コード）と文字列の違いから復習していきます。 pic.twitter.com/ogsLaM6TvD

拡大

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

複数の文字列を２次元配列で持つ場合と大きなバッファ＋ポインタの配列で保つ場合の違いです。後者はメモリを効率よく利用できますし、文字列の入れ替えもポインタの入れ替えですみます。 pic.twitter.com/ZLxhJKrHy3

拡大

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

単一のバッファにどのように文字列を追加し、それをポインタの配列に設定していかの説明です。 pic.twitter.com/wM4hG4d5Q9

拡大

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

具体的にはこのような設定になります。文字列へのポインタを設定したあとにポインタ配列をクイックソートでソートします。 pic.twitter.com/XkPAspbVZA

拡大

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

余談でテキスト処理とか再帰について少しお話しました。また、C言語においては仮引数で宣言する配列とポインタは完全に同一であることも説明しました（スタック上の仮引数は実態はポインタとして存在するので配列として宣言してもポインタと宣言しても１００％同じ意味を持つということ）。 pic.twitter.com/ALyHGonMr0

拡大

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

まとめ。クイックソートの言語化をしてみました。これでクイックソートの分析がおわりました。　おしまい。 pic.twitter.com/EpPI7zM7dL

拡大