Том Сойер играет в сортировку (QuickSort)

Вместо предисловия: вчера сын попросил объяснить на пальцах работу алгоритма QuickSort. В результате появился наглядный пример, в котором удалось показать и общую логику работы и процесс распараллеливания задачи.

Тётушка Полли попросила Тома расставить горшки с цветами у дорожки от калитки к дому, строго по высоте, чтобы самые высокие и пышные кусты стояли у самой улицы, вызывая восхищение у соседей, а постепенное убывание в высоте создало бы эффект перспективы.

Друзья по играм: Бен, Билли, Том Миллер и другие, с интересом ждали правил игры, в которую Сойер превратит задание на этот раз. 

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

— Пропади я пропадом, если не уберу подальше от улицы все кусты, что будут похуже этого!

Том в задумчивости осмотрел ряд таких же кустов.

— Вот второй куст, он повиднее этого! Но почём мне знать насколько он хорош? Пусть пока постоит на месте. Тётушка точно будет недовольна, если мы будем дёргать горшки почём зря.

— Третий тоже повыше моего, оставим и его до срока.

Том медленно пошёл вдоль дорожки, придирчиво сравнивая каждый цветок со своим образцом. У очередного куста от воскликнул:

— Попался, оборванец! Что ж поделать, многоуважаемый недоросль, ваше место займёт более возвышенный кандидат!

Аккуратно поставив образец на дорожку, Том схватил провинившийся горшок и побежал к дому. Пристроив его на пустующее первое блюдце, мальчик с пафосом обратился к соседнему, второму цветку: — Уж даже и не знаю, насколько хороши Вы лично, но Вам точно нечего делать по соседству с этим жалким ничтожеством!

Он схватил второй куст и перенёс его на пустующее место в ряду, возле своего образца.

Поднимая свой образец с земли, Том с жалостью сказал ему: — Судя по всему, дружок,  тебе не украшать собой вход у калитки… Но пойдём дальше, поищем ещё кого-то похуже тебя.

Так он и продвигался от дома к калитке, перенося более хилые цветки на второе, третье и последующее опустевшее место от дома, замещая их следующим более рослым цветком.

— Том, но у тебя же цветки не по росту даже возле дома! — воскликнул Билли.

— И зачем ты звал нас, чёрт бы тебя побрал? Нам скучно! — добавил Бен.

— Пф… Погодите минутку! Я почти закончил свою часть. — Сказал Том, сравнивая свой первый образец с самым последним горшком у калитки.

— Вот смотрите, у меня в руках куст, а в ряду есть одно пустое блюдце. И провались я под землю, если ему не там самое место! — Том, поставил свой образец на пустующее место и задвинул его на шаг от дорожки, разорвав ряд горшков на две части.

— Все кусты, что поближе к дому от этого – ещё унылей чем он, а все что поближе к дороге — получше. Теперь вы понимаете?

— Что мы должны были понять?

— Вы поняли как я нашёл этому горшку самое-пресамое для него место? Его точно уже не придётся таскать сегодня! — сказал Том.

— Сможете повторить?

— Ну, вроде да… — заулыбался Бен.

— Чур, я беру пол-ряда от калитки! — крикнул Миллер.

— А моя половина тогда ближе к дому! — застолбил Бен.

— А как же я? — спросил Билли.

— Не переживай — ответил Том, — сейчас они найдут самое-пресамое место только для первых горшков в своих кусочках ряда и отодвинут их, как бы на якорь поставят. И у нас появится новое веселье в получившихся половинках половинок! И так, пока все кусты не построятся, как на парад.

Тётушка Полли с улыбкой наблюдала за суетой мальчишек из окна и крикнула им: — Не забудьте потом придвинуть горшки обратно к дорожке! А потом чай со сладким!