Quickselect Algorithmus - Vereinfachte Erklärung

Question

Ich habe dies vor HERE gefragt, aber ich möchte die Erklärung der Quickselect (basierend auf Quicksort) vereinfacht weiter zu haben. Die vorherige Frage, die ich gestellt habe, enthielt einen Beispielcode (damit Sie wissen, worum es mir geht).

Ich fragte mich, ob irgendjemand irgendwo an irgendeinem Punkt die Regeln und Richtlinien von quickselect als ein Spiel zusammengefasst hatte, wo man lernen kann, wie der Algorithmus funktioniert, indem man einfach verstandene Regeln befolgt, um ein Kartenspiel zu sagen Zahlen auf Papierbögen.

Ich denke, eine vereinfachte Erklärung des Quickselect-Algorithmus wäre für mich wichtig, um zu verstehen, wie es funktioniert, da die Tutorials und Erklärungen, die ich erhalten habe, schwer zu verstehen und zu visualisieren sind. Selbst die Videos auf Youtube, die Quicksort in einen Tanz verwandeln, haben nicht viel geholfen.

Vielen Dank im Voraus Stack, du warst bisher eine große Hilfe.

Answer 1

Sie gehen in eine Turnhalle mit 200 Kindern. Es ist der 8. September, also hast du einen brennenden Wunsch, das 98. kürzeste Kind zu finden. Du weißt, dass du sie alle vom kürzesten zum höchsten aufstellen kannst, aber das würde ewig dauern. "Ich weiß", denkst du, "ich könnte QUICKSELECT benutzen!"

Sie gehen in die Menge hinaus, schließen Sie Ihre Augen, strecken Sie Ihren Finger aus und drehen Sie sich dreimal um. Wenn Sie Ihre Augen öffnen, zeigen Sie direkt auf eines der Kinder, Peter Pivot. Du sagst: "Schnell! Jeder, der kleiner ist als Peter, kommt hier rüber. Und jeder, der größer ist als Peter, steht da drüben. Wenn du genauso groß bist wie Peter, kannst du in jede Gruppe gehen."

Die Kinder schleichen herum, und bald stehen sie in den beiden Gruppen. Sie zählen und finden 120 Kinder in der kürzeren Gruppe und 79 Kinder in der größeren Gruppe. Sie wissen, dass das 98. kürzeste Kind in der kürzeren Gruppe sein muss, also sagen Sie Peter und den 79 größeren Kindern, dass sie auf der Tribüne sitzen sollen.

Sie wieder schließen Sie die Augen, strecken Sie Ihren Finger aus, und drehen Sie sich dreimal um. Wenn Sie Ihre Augen öffnen, zeigen Sie direkt auf Peters Schwester Paula Pivot. Du sagst: "Schnell! Diejenigen von euch, die immer noch stehen. Wenn du kleiner bist als Paula, komm und stehe hier drüben. Wenn du größer bist als Paula, dann bleib drüben stehen. Wenn du gleich groß bist, kannst du Geh in jede Gruppe. "

Die Kinder schleichen herum, und bald stehen sie in den beiden Gruppen. Sie zählen und finden 59 Kinder in der kürzeren Gruppe und 60 Kinder in der größeren Gruppe. Sie wissen, dass das 98. kürzeste Kind in der größeren Gruppe sein muss, also sagen Sie Paula und den 59 kürzeren Kindern, dass sie auf der Tribüne sitzen.

Sie wieder schließen Sie die Augen, strecken Sie Ihren Finger aus, und drehen Sie sich dreimal um. Wenn Sie Ihre Augen öffnen, zeigen Sie direkt auf Paulas Cousin Prudence Pivot. Du sagst: "Schnell! Diejenigen von euch, die immer noch stehen. Wenn du kleiner bist als Prudence, komm und steh hier drüben. Wenn du größer als Prudence bist, dann bleib drüben stehen. Wenn du genauso groß bist, kannst du Geh in jede Gruppe. "

Die Kinder schleichen herum, und bald stehen sie in den beiden Gruppen. Du zählst und findest 37 Kinder in der kürzeren Gruppe und 22 Kinder in der größeren Gruppe. Du weißt, dass Paula und 59 andere kleinere Kinder auf der Tribüne sitzen. Zusammen mit den 37 kleineren Kindern, die noch stehen, wissen Sie, dass insgesamt 97 Kinder kürzer sind als Prudence. Deshalb ist Prudence das 98. kürzeste Kind!

Quickselect FTW!