HEREの前にこれを尋ねましたが、クイックセレクト（クイックソートに基づく）の説明をさらに簡素化したいと考えています。私が行った前の質問には、いくつかのサンプル コードが含まれていました (つまり、私が何を考えているかがわかります)。
どこかの時点で誰かがクイックセレクトのルールとガイドラインをゲームとして要約していないか疑問に思っていました。ゲームでは、簡単に理解できるルールに従うことでアルゴリズムがどのように機能するかを学ぶことができます。紙。
私が受け取ったチュートリアルと説明はまだ把握して視覚化するのが難しいため、quickselect アルゴリズムの簡単な説明は、それがどのように機能するかを理解する上で最も重要だと思います。クイックソートをダンスに変える YouTube のビデオでさえ、あまり役に立ちませんでした。
よろしくお願いします Stack、これまで大変お世話になりました。
あなたは 200 人の子供がいる体育館に足を踏み入れました。今日は 9 月 8 日なので、98 番目に背の低い子を見つけたいという強い願望があります。背の低いものから高いものまで並べることはできますが、それには時間がかかります。「わかった」、「QUICKSELECTを使えばいいのに！」とあなたは思います。
群衆の中に出て、目を閉じて指を突き出し、3 回回転します。目を開けると、子供の 1 人であるピーター ピボットを直接指しています。あなたは、「急いで！ピーターより背の低い人はここに立ってください。ピーターより背の高い人はあそこに立ってください。ピーターと同じ身長なら、どちらのグループにも入ることができます。」と言います。
子供たちは足を引きずりながら、すぐに 2 つのグループに分かれます。数えてみると、背の低いグループには 120 人の子供がいて、背の高いグループには 79 人の子供がいます。あなたは 98 番目に背の低い子供が背の低いグループに属しているに違いないことを知っているので、ピーターと 79 人の背の高い子供たちに観覧席に座るように言います。
もう一度目を閉じて、指を出して、3 回転します。目を開けると、ピーターの妹、ポーラ・ピボットを直接指しています。あなたは言います、「早く！まだ立っている人たち。ポーラより背が低いなら、ここに立ってください。ポーラより背が高いなら、あそこに立ってください。同じ身長なら、立っていてもいいです。」どちらかのグループに入ってください。」
子供たちは足を引きずりながら、すぐに 2 つのグループに分かれます。数えてみると、背の低いグループには 59 人の子供がいて、背の高いグループには 60 人の子供がいます。あなたは 98 番目に背の低い子供が背の高いグループに属しているに違いないことを知っているので、ポーラと 59 人の背の低い子供たちに観覧席に座るように言います。
もう一度目を閉じて、指を出して、3 回転します。目を開けると、ポーラのいとこであるプルーデンス ピボットを直接指しています。「早く！ まだ立ってる人たちよ。プルーデンスより背が低いならこっちに来て。プルーデンスより背が高いならあそこに立って。同じ身長なら大丈夫。どちらかのグループに入ってください。」
子供たちは足を引きずりながら、すぐに 2 つのグループに分かれます。数えてみると、背の低いグループには 37 人の子供がいて、背の高いグループには 22 人の子供がいます。ポーラと他の 59 人の背の低い子供たちが観覧席に座っていることを知っています。まだ立っている 37 人の背の低い子供に加えて、合計 97 人の子供がプルーデンスより背が低いことがわかります。したがって、プルーデンスは 98 番目に背の低い子です。
クイックセレクトFTW！