Алгоритмы 101: как использовать сортировку слиянием и быструю сортировку в JavaScript

Введение в алгоритмы сортировки

Алгоритм сортировки — это алгоритм, используемый для изменения порядка элементов в списке или массиве в соответствии с конкретным требованием. Например, алгоритмы сортировки могут организовать массив элементов от наименьшего к наибольшему.

Эффективный алгоритм сортировки важен для оптимизации эффективности других алгоритмов (таких как алгоритмы поиска и сжатия).

Алгоритмы сортировки состоят из серии инструкций. Они принимают массив или список в качестве входных данных, выполняют операции и выводят отсортированный массив.

Существует ряд популярных алгоритмов сортировки. Девять самых популярных :

• Пузырьковая сортировка
• Сортировка вставкой
• Сортировка слиянием
• Быстрая сортировка
• Сортировка по выбору
• Сортировка с подсчетом
• Сортировка по сегментам
• Радиксная сортировка
• Heapsort

Алгоритм сортировки слиянием

Сортировка слиянием — это эффективный универсальный алгоритм сортировки, основанный на сравнении. Он работает путем рекурсивного деления массива на две равные половины, сортировки и последующего объединения каждой отсортированной половины..

Возьмите массив [10, -1, 2, 5, 0, 6, 4, -5] . Вот как к этому подошла бы сортировка слиянием.

Реализации сортировки слиянием и быстрой сортировки являются примерами алгоритма «разделяй и властвуй». Вообще говоря, алгоритм «разделяй и властвуй» состоит из следующих частей:

• Divide: Это включает разделение проблемы на подзадачи
• Conquer: рекурсивно обрабатывать подзадачи, пока каждая из них не будет решена.
• Объединить: объединить решенные подзадачи, чтобы получить решение исходной проблемы.

Сортировка слиянием может использоваться для всех видов проблем. Три наиболее распространенных применения сортировки слиянием — это сортировка связанных списков в O ( n L o g n ) O (nLogn) Время O (nLogn), проблема количества инверсий и внешняя сортировка.

Реализация в JavaScript

Ниже приведена реализация кода алгоритма сортировки слиянием в JavaScript. Алгоритм состоит из двух функций:

• Функция mergeSort () , которая заботится о разбиении массивов.
• Функция merge , которая объединяет отдельные массивы

 function mergeSort (array) {if (array.length === 1) {return array;  } const middle = Math.floor (array.length/2);  const left = array.slice (0, в середине);  const right = array.slice (посередине);  return merge (mergeSort (слева), mergeSort (справа));} функция merge (слева, справа) {let result = [];  пусть leftIndex = 0;  пусть rightIndex = 0;  while (leftIndex  
 
     
 
 

Давайте попробуем разобрать, что происходит:

1. Если в массиве только один элемент, мы возвращаем массив и завершаем работу (Базовый случай)
2. В противном случае мы разделяем массив на две половины максимально равной длины (Divide)
3. Используя рекурсию, мы сортируем оба массива с помощью mergeSort () код> функция. (Завоевание)
4. Наконец, мы объединяем два отсортированных массива и возвращаем результат. (Объединить)

Итак, возьмем массив, который мы использовали в примере выше. Давайте посмотрим, как мы реализуем сортировку слиянием в коде JavaScript.

 function mergeSort (unsortedArray) {if (unsortedArray.length  
 
     
 
 

Временная и пространственная сложность

Сортировка слиянием имеет гарантированную временную сложность O ( n l o g n ) O (nlogn) O (nlogn ), что значительно быстрее, чем среднее и худшее время работы нескольких других алгоритмов сортировки. Сортировка слиянием — это стабильная сортировка со сложностью пространства O ( n ) O (n) O (n).

• Вспомогательное пространство: O ( n ) O (n) O (n)
• Алгоритмическая парадигма: разделяй и властвуй
• Сортировка на месте: Нет
• Стабильный: Да

Сравнение с другими алгоритмами сортировки

На практике сортировка слиянием немного медленнее, чем быстрая сортировка. Это также не так компактно, как реализация Quicksort на месте. MergeSort обычно предпочтительнее QuickSort для связанных списков из-за разницы в распределении памяти.

Алгоритм быстрой сортировки

Как и сортировка слиянием, быстрая сортировка является алгоритмом разделения и владения, но работает немного иначе. Быстрая сортировка начинается с выбора элемента поворота из массива и разделения других элементов на два подмассива в зависимости от того, больше они или меньше, чем точка поворота. Затем подмассивы рекурсивно сортируются.

Алгоритм быстрой сортировки не использует лишнего места, поскольку сортировка выполняется на месте.

Этот алгоритм может выбрать опорный элемент несколькими способами.

• Выбрать первый элемент как опорный.
• Выбрать последний элемент как точка поворота
• Выбрать случайный элемент в качестве точки поворота.
• Выбрать медианную точку в качестве точки поворота

Реализация в JavaScript

Ключевой процесс ниже — это наша функция разделения , которая выбирает нашу точку опоры. В этой реализации это делается с помощью схемы разделов Хоара , которая работает путем инициализации двух индексов, начинающихся с концов массива. Индексы перемещаются друг к другу, пока не будет обнаружена инверсия.

Инверсия — это пара элементов, один больше или равен оси поворота, один меньше или равен, которые расположены в неправильном порядке относительно друг друга. Затем инвертированные значения меняются местами, и процесс повторяется.

Выбор хорошей точки поворота — ключ к быстрой реализации Quicksort. На практике алгоритмы быстрой сортировки используют рандомизированный сводный график, ожидаемая временная сложность которого составляет O ( n l o g n ) O (n log n) O (nlogn).

 функция partitionHoare (array, left,  справа) {const pivot = Math.floor (Math.random () * (right - left + 1) + left);  while (left  массив [точка]) {right--;  } если (слева  точка поворота) {быстрая сортировка (массив, точка поворота, вправо);  } return array;} 

Сложность времени

Алгоритм быстрой сортировки имеет временная сложность O ( n l o g n ) O (n log n) O (nlogn). В худшем случае это становится O ( n 2 ) O (n2) O (n2 ). Пространство, используемое Quicksort, зависит от используемой версии.

Оперативная версия Quicksort имеет сложность пространства O ( l o g n ) O (log n) O (logn), даже в худший случай, в то время как сложность пространства в среднем случае равна O ( n ) O ( n ) . O (n) O (n). O (n ) O (n).

• Алгоритмическая парадигма: разделяй и властвуй
• Сортировка на месте: Да
• Стабильный: По умолчанию нестабильный

Сравнение с другими алгоритмами сортировки

В то время как среднее время работы Quicksort в лучшем случае такое же, как и у других алгоритмов, таких как Merge Sort, хорошо реализованная Quicksort будет иметь гораздо меньшее время. постоянные коэффициенты, чем другие алгоритмы сортировки.

На практике Quicksort часто быстрее, чем сортировка слиянием.

В случае Quick Сортировка в общем виде представляет собой сортировку на месте (т. Е. не требует дополнительного хранилища). Для сортировки слиянием требуется O ( N ) O (N) O (N) дополнительное хранилище, где N N N обозначает размер массива, который может быть довольно большим.

Чему научиться дальше

Сортировка — основа многих сложных программных решений. Хотя это может показаться простой концепцией, сортировка является одним из многих типов алгоритмов, протестированных на собеседовании по кодированию.

На практике эффективность или скорость алгоритма сортировки иногда может зависеть от типа данных. набор сортируется. Далее вам следует изучить следующие алгоритмы:

• Сортировка вставкой
• Пузырьковая сортировка
• Сортировка по выделению
• Heapsort
• Bucket Sort

Чтобы начать работу с этими концепциями, ознакомьтесь с планом обучения Educative Ace the Front end Interview. Вы изучите все ключевые концепции CSS, HTML и JavaScript, которые вам необходимо знать, попрактикуясь и погрузившись в десятки реальных вопросов. К тому времени, как вы закончите, вы сможете решать все, что встречается на собеседовании..

Удачного обучения!

Читать далее о JavaScript

• Методы массива JavaScript: как использовать карту и уменьшить
• 7 структур данных JavaScript, которые вы должны знать
• Алгоритмы 101: как проверить, является ли строка палиндромом