Программисты именуют этот способ довольно логично – сортировкой методом вставок.
Хорошая новость в том, что это, возможно, еще более интуитивно понятный метод, чем пузырьковая сортировка, и у него отнюдь не плохая репутация. Плохая новость в том, что этот способ занимает не меньше времени. Вам все равно приходится ставить на полку по одной книге за раз. Каждый раз нужно просматривать в среднем около половины стоящих на полке книг и находить правильное место для следующей книги. Хотя на практике процесс сортировки методом вставок идет немного быстрее, чем пузырьковая сортировка, мы все равно имеем дело с квадратичным временем. Сортировка более одной книжной полки все равно становится нелегкой задачей.
Прохождение через квадрат: дели и побеждай
После рассмотрения двух абсолютно разумных подходов, которые переходят в плоскость нерационального квадратичного времени, напрашивается вопрос: а существуют ли способы ускорить процесс сортировки?
Вопрос, по сути, о продуктивности. Но если обсудить этот вопрос с программистом, то он становится ближе к метафизике – сродни размышлениям о скорости света, путешествиях во времени, сверхпроводниках и термодинамической энтропии.
Каковы фундаментальные законы и границы вселенной? Что возможно? Что позволено? Так программисты пытаются узреть божьи планы наряду с учеными в области физики частиц и космологии.
Каково минимальное усилие, необходимое для установления порядка?
Возможно ли найти параметр сортировки О(1) (как в случае уборки дома перед приездом компании друзей), по которому можно было бы сортировать любой объем единиц за равное количество времени?
В принципе мы даже не можем утверждать, что процесс сортировки n книг на полке постоянен во времени, поскольку он требует проверки n книг, и это количество, по сути, конечно. Поэтому сортировка книг в условиях временной константы даже не обсуждается.
А если рассмотреть параметр линейного времени О(n), который подобен передаче блюд по кругу за столом, когда удвоение количества объектов удваивает и объем работы? Размышляя о вышеописанных примерах, сложно представить, как же они могут работать. Значение n2 в каждом из этих случаев мы получаем в связи с необходимостью переместить n книг, и работа, которую мы должны проделать при каждом перемещении книги, пропорциональна значению n. Так как же нам уйти от n в степени n и вернуться к самой величине n? При пузырьковой сортировке мы получили значение O(n2) применительно ко времени выполнения задачи, исходя из манипуляций с каждой из n книг и перемещения каждой из них с места на место