Пузырьковая сортировка неэффективна. Как действительно действительно очень неэффективно. Но, видите ли, я не знал этого, когда впервые начал изучать C++, поэтому с ручкой и бумагой, пока я сидел в исчислении, я написал пузырьковую сортировку, список из десяти чисел, и начал сортировать их вручную.
Мне нравится играть в игры. Если бы я мог вынести это чувство, когда я ставлю себе счет, зная, что его можно побить, а затем работаю над тем, чтобы в конечном итоге забить этот счет в капсулу, я был бы наркоманом. Когда дело дошло до сортировки моих небольших рукописных списков чисел, параллели сразу же стали очевидны. Как человеку, которому не нравится писать, первое, что меня заботило, — это количество проходов, которые должен пройти алгоритм, прежде чем список будет отсортирован. Как только я начал превращать свои каракули в код и помещать их в XCode, я гнался за временем. Это стало игрой в миллисекундный гольф, которая продолжается и сегодня. Обратите внимание: я не ожидаю, что что-то из того, что я сделал, будет новым. Я уверен, что все это было сделано раньше. Это больше обо мне, чем о пузырьковой сортировке.
Начнем с рассмотрения общей пузырьковой сортировки. Это выглядит примерно так.
Основная идея заключается в том, что он проходит через массив, и если индекс после того, на который вы смотрите, меньше, вы меняете их местами и устанавливаете sorted на false. Если в последнем проходе произошли какие-либо замены, повторите все заново. Если нет, то список отсортирован.
Вот как это выглядит. Каждая строка представляет один проход. Используя этот алгоритм, сортировка списка, содержащего 1 миллион случайно сгенерированных целых чисел, занимает 2242928,0 мс. Это примерно 37 с лишним минут. Это абсурдно долго. Итак, что мы можем сделать, чтобы это исправить? Давайте начнем с рассмотрения того, где эта базовая пузырьковая сортировка терпит неудачу.
Если вы будете следить за числами на каждом проходе, вы заметите несколько вещей. Первый заключается в том, что 10 сразу же вставляется в нужное положение. Это связано с тем, что пузырьковая сортировка по своей природе будет вытеснять самый высокий элемент, оставшийся вне позиции, во время каждого прохода в позицию. Это действительно хорошая функция. Мы автоматически знаем, что некоторые элементы сортируются после каждого прохода, и поэтому можем игнорировать эти элементы.
При этом наше время сокращается до 1626360,0 мс или 27 минут и 58 секунд, что кажется странным. Это не так много! Почему? Пренебрегая последними элементами в списке, мы избавляемся от некоторых ненужных сравнений, но количество перестановок остается прежним. К сожалению, подкачка — это то, на что тратится большая часть времени, поэтому ограничение сравнений не помогает нам так сильно, как можно было бы надеяться.
Итак, как мы это делаем? Это первое решение, которое я придумал, когда сидел на уроке математического анализа. Что мы собираемся сделать, так это начать с концов массива (первый и последний элементы) и двигаться к центру, сравнивая и меняя местами по мере необходимости. В приведенном выше примере 10 нужно было поменять местами по всему списку, что требует значительных вычислительных ресурсов. Вместо этого, меняя местами с противоположных концов списка, нам удается перемещать элементы, оказавшиеся далеко от их законных позиций, на приличное расстояние ближе, что позволяет сортировке быть гораздо менее затратной в вычислительном отношении!
При этом мы сокращаем наше время до 1095600,0 мс или 18 минут и 49 секунд. Мы сократили исходное время более чем на треть! Насколько это здорово? По словам покойного Билли Мэйса: «Но подождите! Есть больше!" Я еще раз напомню вам, дорогой читатель, что код, который вы сейчас увидите, был написан, когда я только начинал знакомиться с C++. DRY был для меня совершенно чужим. Я говорю вам это, чтобы вы не обидели меня, когда увидите это чудовище:
Мне так, так жаль. Действительно я. Надеюсь, вы простите меня, если я объясню. Мне не потребовалось много времени, чтобы понять, что путем дальнейшего подразделения массива, а затем предварительной сортировки подкачки для каждого подразделения, мы можем еще больше снизить общий объем подкачки, но я был идиотом, поэтому я выбрал лучший способ сделать было бы вручную. Эта программа из более чем тысячи строк, на которую вы смотрите, является результатом того, что я считал лучшим способом сортировки местами всего массива, а затем пополам, четвертям, 8-м, 16-м, 32-м и 64-м. Однако весь этот дерьмовый код окупился, потому что целочисленный массив из 0 миллиона элементов теперь можно отсортировать за 25650,0 мс. Это примерно 26 секунд или примерно 1/70 времени нашей исходной пузырьковой сортировки.
В тот момент, когда я был в своем образовании, я не мог идти дальше, если я не хотел потратить несколько часов на копирование / вставку, так что тогда это было для меня. Но, конечно, я сижу и пишу это, так что у меня должна быть причина, верно? Вы правы! Я продолжил с того места, где остановился несколько дней назад, и той же ночью закончил гораздо более короткую версию 2.0. Вот эта версия 2.0.
Что я здесь сделал? Во-первых, я свернул этот массивный блок из версии 1.0, чтобы взгляд на него не только больше не вызывал дизентерию, но и продолжал делиться до тех пор, пока не перестал. Общее время выполнения: 9162,0 мс или 1/200 от исходного. Но я все еще не удовлетворен, поэтому пойдем немного дальше.
Между вышеизложенным и тем, что я пишу сейчас, прошло несколько месяцев, так что потерпите меня немного здесь. Я превратил свою пузырьковую сортировку в сортировку в шейкере, которая является двунаправленной версией пузырьковой сортировки. Делая это, я знаю, что один дополнительный элемент на обоих концах массива остается на месте после каждого прохода. Я также адаптировал часть сортировки подкачки, чтобы игнорировать элементы на месте, а не проверять их при каждом проходе. С учетом этого и некоторых настроек мы сократились до ~ 3150 мс или 1/712 от оригинала.
Однако после всего этого я подозреваю, что смогу выжать немного больше скорости из этой штуки, если буду сортировать пузырьком только в одном направлении и учитывать это при сортировке подкачки. Давайте посмотрим, почему.
Обратите внимание, что при смещении всей сортировки на один элемент каждый раз, а не при отрезании концов, сравниваемые элементы с большей вероятностью будут отличаться от элементов, сравниваемых на предыдущем проходе. Делая это, мы также можем реализовать другой метод оптимизации пузырьковой сортировки. Иногда случайно может оказаться более одного значения. Мы можем обнаружить это, отслеживая последний замененный элемент и сравнивая эту точку.
Но я думаю, что я собираюсь закончить с этим клиффхэнгером. Я боюсь, что если я не опубликую это сейчас, то продолжу заниматься этой проблемой и никогда ничего не опубликую, а какой смысл кодить, если твою работу никто никогда не увидит?
Таким образом
Продолжение следует…
