Эффективная сортировка с помощью JavaScript: реализация алгоритма сортировки слиянием

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

Что такое сортировка слиянием?

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

Как реализовать сортировку слиянием с помощью JavaScript?

Вот пошаговое руководство о том, как реализовать сортировку слиянием с помощью JavaScript:

Шаг 1: Создайте функцию для рекурсивного разделения входного массива на две половины.

javascriptCopy codefunction mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  }
  const middleIndex = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, middleIndex);
  const rightArr = arr.slice(middleIndex);
  return merge(mergeSort(leftArr), mergeSort(rightArr));
}

Функция mergeSort принимает массив в качестве входных данных и проверяет, содержит ли массив только один элемент. Если это так, он возвращает массив, поскольку он уже отсортирован. Если нет, он разбивает массив на две половины с помощью метода slice и рекурсивно вызывает mergeSort для каждой половины. Функция merge используется для слияния двух половин.

Шаг 2: Создайте функцию для объединения двух отсортированных массивов в один отсортированный массив.

function merge(leftArr, rightArr) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      result.push(leftArr[leftIndex]);
      leftIndex++;
    } else {
      result.push(rightArr[rightIndex]);
      rightIndex++;
    }
  }
  return result.concat(leftArr.slice(leftIndex)).concat(rightArr.slice(rightIndex));
}

Функция merge принимает два отсортированных массива в качестве входных данных и инициализирует пустой массив для хранения отсортированного вывода. Затем он сравнивает первые элементы каждого массива и добавляет меньший элемент в выходной массив. Процесс продолжается до тех пор, пока все элементы одного массива не будут добавлены в выходной массив. Затем он объединяет оставшиеся элементы другого массива с выходным массивом.

Шаг 3: Протестируйте функцию с помощью примера входных данных.

const arr = [8, 4, 2, 7, 6, 1, 5, 3];
console.log(mergeSort(arr));

В этом примере мы создаем массив несортированных целых чисел и передаем его функции mergeSort. На выходе будет отсортированный массив [1, 2, 3, 4, 5, 6, 7, 8].

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