Алгоритм быстрого выбора - Упрощенное объяснение

Я спросил это раньше ЗДЕСЬ, однако я хочу, чтобы объяснение quickselect (на основе quicksort) упростилось дальше. Предыдущий вопрос, который я задал, включал некоторый пример кода (так что вы знаете, о чем я говорю).

Мне было интересно, если кто-нибудь в любой момент подвел итоги правилам и рекомендациям quickselect в качестве игры, где можно узнать, как работает алгоритм, следуя легко понятным правилам, которые можно применить, чтобы сказать колоду карт или цифр на битах бумаги.

Я думаю, что упрощенное объяснение алгоритма quickselect было бы первостепенным для меня, чтобы понять, как он работает, поскольку все же урок и объяснения, которые я получил, трудно понять и визуализировать. Даже видео на YouTube, которые превращают quicksort в танец, не помогли.

Спасибо, Stack, вы были большой помощью до сих пор.

Ответ 1

Вы идете в гимназию, в которой есть 200 детей. Это 8 сентября, поэтому у вас есть горячее желание найти 98-го младшего ребенка. Вы знаете, что вы можете направить их всех от самых коротких до самых высоких, но это займет навсегда. "Я знаю", вы думаете: "Я мог бы использовать QUICKSELECT!"

Вы выходите в толпу, закрываете глаза, торчите пальцем и вращаетесь три раза. Когда вы открываете глаза, вы указываете прямо на одного из детей, Питера Пивота. Вы говорите: "Быстро! Все короче, чем Питер, встаньте здесь, и все выше, чем Питер, встаньте там. Если вы такая же высота, как Питер, вы можете пойти в обе группы".

Дети перетасовываются, и вскоре они стоят в двух группах. Вы считаете и находите 120 детей в более короткой группе и 79 детей в более высокой группе. Вы знаете, что 98-й самый младший ребенок должен быть в более короткой группе, поэтому вы говорите Петру и 79 высоким детям сидеть в трибунах.

Вы снова закрываете глаза, торчаете пальцем и вращаетесь три раза. Когда вы открываете глаза, вы указываете прямо на сестру Питера Паулу Пивот. Вы говорите: "Быстро! Те из вас, кто все еще стоит. Если вы короче Паулы, придите сюда. Если вы выше Паулы, встаньте там. Если вы на той же высоте, вы можете перейдите в обе группы".

Дети перетасовываются, и вскоре они стоят в двух группах. Вы считаете и находите 59 детей в более короткой группе и 60 детей в более высокой группе. Вы знаете, что 98-й самый младший ребенок должен быть в более высокой группе, поэтому вы говорите Пауле и 59 коротким детям сидеть в трибунах.

Вы снова закрываете глаза, торчаете пальцем и вращаетесь три раза. Когда вы открываете глаза, вы указываете прямо на кузен Паулу, Пруденс Пивот. Вы говорите: "Быстро! Те из вас, кто все еще стоит. Если вы короче, чем Пруденс, встаньте здесь. Если вы выше Пруденс, встаньте там. Если вы такая же высота, вы можете перейдите в обе группы".

Дети перетасовываются, и вскоре они стоят в двух группах. Вы считаете и находите 37 детей в более короткой группе и 22 ребенка в более высокой группе. Вы знаете, что Паула и 59 других более коротких детей сидят на трибунах. Наряду с 37 короткими детьми, которые все еще стоят, вы знаете, что в общей сложности 97 детей короче, чем Пруденс. Поэтому Пруденс - это 98-й самый короткий ребенок!

Quickselect FTW!