Сортировка слиянием и быстрая сортировка - это алгоритмы «разделяй и властвуй», распространенные в программах на JavaScript. Читайте дальше, когда мы обсудим, как их использовать

Эта статья написана Джерри Эджонави.

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

Хотя от вас, возможно, не потребуется внедрять алгоритм сортировки в повседневной работе как разработчика программного обеспечения, важно знать, как некоторые из этих алгоритмов работают внутри компании. Это обычное дело для собеседований по кодированию и делает вас более эффективным разработчиком.

В сегодняшней статье мы рассмотрим два самых популярных алгоритма сортировки: сортировку слиянием и быструю сортировку. Это важно для ваших основ информатики и оптимизации кода.

Сегодня мы узнаем:

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

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

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

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

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

  • Пузырьковая сортировка
  • Вставка сортировки
  • Сортировка слиянием
  • Быстрая сортировка
  • Выборочная сортировка
  • Счетная сортировка
  • Ковшовая сортировка
  • Radix sort
  • Heapsort

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

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

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

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

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

Сортировку слиянием можно использовать для решения самых разных задач. Три наиболее распространенных применения сортировки слиянием - это сортировка связанных списков за время 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, middle);
  const right = array.slice(middle);
  return merge(
     mergeSort(left),
     mergeSort(right)
  );
}
function merge(left, right) {
 let result = [];
 let leftIndex = 0;
 let rightIndex = 0;
 while (leftIndex < left.length && rightIndex < right.length) {
   if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
   } else {
      result.push(right[rightIndex]);
      rightIndex++;
   }
 }
 return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

Попробуем разобраться в происходящем:

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

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

function mergeSort (unsortedArray) {
  if (unsortedArray.length <= 1) {
    return unsortedArray;
  }
  // In order to divide the array in half, we need to find middle
  const middle = Math.floor(unsortedArray.length / 2);
  const left = unsortedArray.slice(0, middle);
  const right = unsortedArray.slice(middle);
  // Use recursion to combine the left and right
  return merge(
    mergeSort(left), mergeSort(right)
  );
}

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

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

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

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

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

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

Как и сортировка слиянием, быстрая сортировка - это алгоритм «разделяй и властвуй», но он работает немного иначе.

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

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

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

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

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

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

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

Выбор удачного поворота - ключ к быстрому внедрению быстрой сортировки. На практике алгоритмы быстрой сортировки используют рандомизированную опорную точку, которая имеет ожидаемую временную сложность O (n log n).

function partitionHoare(array, left, right) {
  const pivot = Math.floor(Math.random() * (right - left + 1) + left);
  while (left <= right) {
    while (array[left] < array[pivot]) { 
       left++;
    } 
    while (array[right] > array[pivot]) {
      right--;
    }
    if (left <= right) {
      [array[left], array[right]] = [array[right], array[left]];
    }
  }
  return left;
}
function quicksort(array, left, right) {
  left = left || 0;
  right = right || array.length - 1;
  const pivot = partitionHoare(array, left, right);
  if (left < pivot - 1) {
     quicksort(array, left, pivot - 1);
  }
  if (right > pivot) {
     quicksort(array, pivot, right);
  }
  return array;
}

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

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

Локальная версия быстрой сортировки имеет пространственную сложность O (log n) даже в худшем случае, в то время как пространственная сложность в среднем случае равна O (n) O (n).

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

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

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

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

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

Что изучать дальше

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

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

  • Вставка сортировки
  • Пузырьковая сортировка
  • Выборочная сортировка
  • Heapsort
  • Ковшовая сортировка

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