!). Это категория задач столь бесчеловечно трудных, что программисты упоминают их только в шутку (как мы, говоря, например, о сортировке колоды до победного конца) или когда им на самом деле очень-очень хотелось бы пошутить.
Квадраты: «пузырьковая» сортировка и сортировка методом вставок
Когда Обама, находясь еще в статусе сенатора, в 2007 году посетил офис Google, глава компании Эрик Шмидт в шутку начал общение в манере собеседования и задал вопрос, как лучше отсортировать миллион 32-битных целых чисел. Обама саркастически улыбнулся и без промедления ответил: «Думаю, пузырьковая сортировка здесь не подойдет». Толпа инженеров Google разразилась аплодисментами.
«Он меня поразил пузырьковой сортировкой», – вспоминал один из них позднее. Обама был прав, что сразу отверг «этот алгоритм, который стал чем-то вроде боксерской груши для студентов-программистов: он достаточно прост, интуитивно понятен и весьма эффективен».
Представьте, что вы хотите расставить в алфавитном порядке одну из ваших книжных коллекций. Самым естественным подходом в этом случае было бы просмотреть книги на полке, чтобы выявить неупорядоченные пары (Уоллес, который «стоит» перед Пинчоном, к примеру) и поменять их местами. Поставьте Пинчона перед Уоллесом, затем продолжите осмотр полки, каждый раз возвращаясь к ее началу. Когда вы просмотрите всю полку и больше не найдете пар, стоящих в неправильном порядке, ваша задача будет выполнена.
Это и есть пузырьковая сортировка, и она погружает нас в квадратичное время. Есть n неупорядоченных книг, и в результате каждого осмотра полки вы можете переставить только одну книгу на другое место (решаем проблемы по мере поступления). То есть в худшем случае, если все книги на полке стоят в обратном порядке, то по меньшей мере одну книгу придется переставить на другое место n раз. Таким образом, мы получаем максимум n осмотров полки, на которой стоит n книг, то есть O(n2) в худшем случае[8]. Но это не слишком ужасно по одной причине: это в миллион раз лучше, чем наша идея сортировки «до победного конца» по формуле O(n!) из предыдущего кейса. И все же вместе с тем этот квадратный корень может очень скоро вас напугать. Например, квадратный корень означает, что сортировка пяти книжных полок займет не в пять раз больше времени, чем сортировка одной, а в 25 раз больше.
В принципе вы можете взять и другой курс – вытащить все книги из шкафа и поставить их в правильном порядке одну за другой. Вы поставите первую книгу в середине полки, затем возьмете вторую, сравните ее с первой и поставите ее либо справа, либо слева от первой книги. Взяв третью, вы просмотрите книги, которые уже стоят на полке, слева направо и определите для нее нужное место. Повторяя этот процесс, вы постепенно расставите все книги на полке в нужном порядке, и ваша миссия будет выполнена.