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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализации сортировки слиянием и быстрой сортировки

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

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

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

Реализация на 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)О ( н л о г н )время, которое значительно быстрее, чем среднее и худшее время работы нескольких других алгоритмов сортировки. Сортировка слиянием — это стабильная сортировка с пространственной сложностьюНа)О ( п ).

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

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

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

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

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

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

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

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

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

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

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

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

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 (п войти п)О ( н л о г н ). В худшем случае это становитсяO (n2)О ( п 2 ). Пространство, используемое Quicksort, зависит от используемой версии.

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

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

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

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

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

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

Читайте также:  Языки функционального программирования: полное руководство
Оцените статью
bestprogrammer.ru
Добавить комментарий