На Stackoverflow — полезнейшее обсуждение насущной мужской задачи сортировки носков. Наивная (“в лоб”) имплементация выглядит так: берете первый носок из кучи, потом начинаете подбирать другой такой же из той же кучи. Очевидно, что время полной сортировки в таком случае пропорционально квадрату от числа носков в куче. Есть ли способ лучше?
Конечно, есть! На самом деле задача сортировки носков — задача группировки. Для этого используем алгоритм хэширования:
1. Каждый носок из кучи добавляем в группу своего цвета. В итоге у нас должно получиться столько групп носков, сколько разных цветов носков у нас есть. Посмотрел сейчас у себя: в наличии имеются черные, белые и светло-коричневые.
2. Проходимся по каждой группе и разбиваем ее на подгруппы по какому-либо атрибуту (рисунку, размеру, типу ткани и т.д.).
3. Рекурсивно повторяем шаг 2 для каждой из подгрупп, пока не получим достаточно маленькие группы, внутри которых сортировку можно произвести с одного взгляда, прямым перебором.
Вуаля! Задача хорошо параллелится (это значит, что вы можете привлечь других членов семьи себе на помощь), а ее сложность — O(n), то есть линейно зависит от числа носков в куче. Здорово, правда? Математика на службе домашнего хозяйства!
P.S. Жена, прочитав обсуждение, хмыкнула и сказала, что давно уже “хэширует” носки именно так. Приятно быть женатым на умной женщине.