Усложним задачу. Пусть нам требуется найти минимальный элемент в неупорядоченном массиве. В жизни мы сталкиваемся с такой задачей, когда пытаемся в магазине найти самый дешевый товар из нужной нам категории. Эта задача также имеет линейную сложность, и для поиска минимального (максимального) элемента в неупорядоченном массиве требуется n – 1 сравнений.
Как будет действовать человек, который в магазине ищет самый дешевый сыр? Он будет последовательно просматривать ценники на сырах, и держать в уме стоимость самого дешевого сыра из тех, которые он уже посмотрел. Если он увидит еще более дешевый сыр, то он запомнит новую цену, и все дальнейшие цены будет сравнивать уже с ней. Запишем этот алгоритм более формально.