Концепция сортировки часто используется при разработке на стороне сервера и является фундаментальной для информатики.
На моем пути к тому, чтобы стать разработчиком программного обеспечения, я обнаружил, что алгоритмы сортировки очень увлекательны, и хотел бы помочь другим на том же пути понять два наиболее известных алгоритма: пузырьковая сортировка и сортировка слиянием.
В следующих разделах я расскажу вам о реализации обоих алгоритмов в JavaScript - псевдокода и всего остального, - чтобы помочь вам укрепить ваше понимание того, как самостоятельно реализовать аналогичные типы. Я не считаю себя экспертом по алгоритмам; все еще очень много учусь. По этой причине я буду использовать вспомогательные функции для реализации этих решений. Это дает нам дополнительное преимущество в виде более декларативного кода (т.е. кода, который больше похож на простой английский), когда мы берем все это в конце.
Пузырьковая сортировка: алгоритм сравнения
Пузырьковая сортировка использует итеративный подход - циклическое перебор элементов матричным способом - к сортировке и является отличным местом для начала реализации вашего первого алгоритма сортировки.
Вот как это работает: учитывая несортированный массив, мы передаем каждый элемент на всю его длину; сравнивая его с элементом рядом с ним. Если первый элемент больше второго, мы меняем местами два элемента.
Это создает эффект «пузырьков», когда самые маленькие элементы (в нашем случае числа) перемещаются в начало списка с каждым проходом.
Как я упоминал ранее, использование вспомогательных функций для реализации пузырьковой сортировки делает код более читаемым, поэтому я начну с их реализации:
Функция парного компаратора
Во-первых, мы определим чистую вспомогательную функцию - функцию, которая принимает входные данные и выдает нам выходные данные, ничего не меняя, - называемую inAscendingOrder. Эта функция берет два элемента в данном массиве, сравнивает их и возвращает логическое значение на основе результата.
Функция подкачки
Затем мы определим функцию, которая меняет местами два элемента в списке. Мы не можем назвать это чистой функцией. Почему? Потому что это действительно повлияет на внешнюю область видимости (нашу реализацию пузырьковой сортировки), когда мы будем ее использовать позже.
Фактическая реализация пузырьковой сортировки
И, наконец, мы хотим определить реальный алгоритм пузырьковой сортировки.
Прежде чем я приведу код, я хочу упомянуть пару вещей, которые может быть полезно понять:
(1) Я собираюсь использовать концепцию «состояния», что в основном означает, что моя функция будет хранить метаданные на себе и сообщать нам, когда она завершит сортировку входного массива;
(2) Я собираюсь пройти через массив в обратном направлении. Что это означает? Что ж, мы используем вложенные циклы для реализации пузырьковой сортировки. Внешний цикл обрабатывает направление и длину наших проходов, поэтому я начну цикл с последнего элемента массива и перейду к индексу 0. Почему мы идем в обратном направлении? Это заставляет его так что внутренний цикл for, цикл, который будет обрабатывать свопинг, требует меньше усилий для выполнения своей работы; избегая дополнительной задачи передачи уже отсортированных элементов. Надеюсь, вы поймете, что я имею в виду ниже:
Сортировка слиянием: алгоритм рекурсивной сортировки
С другой стороны, сортировка слиянием использует подход к сортировке по принципу «разделяй и властвуй»; рекурсивно разбивая входной массив, пока мы не отсортировали подмассивы размером с кортеж, которые затем можно было бы снова объединить вместе в конце.
Я также буду использовать вспомогательные функции для реализации сортировки слиянием (опять же, чтобы код оставался декларативным):
Вспомогательная функция разделения
Вспомогательная функция слияния
Примечание. Анализируя код, вы можете задаться вопросом: подождите, почему она просто не использовала встроенный в javascript метод сдвига для реализации этой функции слияния. Это связано с тем, что использование сдвига потребует от нашего алгоритма большей работы, когда придется пропускать каждый элемент и сдвигать каждый по одному, тем самым замедляя работу. Чтобы оптимизировать эффективность mergeSort, мы хотим сохранить это как линейную операцию (подробнее об этом позже).
И, наконец, вот наше рекурсивное решение сортировки слиянием, которое использует обе вспомогательные функции ...
Сравнение пузырьковой сортировки и сортировки слиянием: анализ сложности времени
Так зачем выбирать одно вместо другого?
У обоих есть свои плюсы и минусы, но в конечном итоге пузырьковая сортировка быстро становится менее эффективной, когда дело доходит до сортировки больших наборов данных (или «больших данных»). Где as, сортировка слиянием становится более эффективной по мере роста наборов данных.
Это станет более понятным, если вы познакомитесь с нотацией большого О и концепцией временной сложности. Что такое временная сложность? По сути, мы используем временную сложность для анализа производительности алгоритма или того, сколько времени требуется для решения проблемы для заданных входных данных. Вот шпаргалка, которая поможет вам глубже разобраться в этом.
В лучшем случае с меньшими наборами данных пузырьковая сортировка имеет O (n), а в худшем случае - временную сложность O (n²) (что довольно плохо).
С другой стороны, сортировка слиянием выполняется довольно стабильно, с временной сложностью O (n log (n)). Временная сложность наших вспомогательных функций для сортировки слиянием делает это возможным.
Есть еще много других алгоритмов сортировки, которые нужно изучить, и я надеюсь, что это поможет другим, кто занимается разработкой программного обеспечения, машинным обучением и другими дисциплинами, лучше понять два самых популярных из них.
