В этой статье мы узнаем о трех распространенных алгоритмах сортировки: пузырьковой сортировке, сортировке выбором и сортировке слиянием. Мы рассмотрим, для чего они полезны, а также как реализовать их в JavaScript. Алгоритм, лежащий в основе этого встроенного метода, реализуется по-разному в зависимости от того, какой браузер вы используете.

Введение в сортировку

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

[3, 8, 5, 9, 1, 2] -> [1, 2, 3, 5, 8, 9]

Если вы разработчик JavaScript, вам может прийти на ум sort() метод массива.

console.log([3, 8, 5, 9, 1, 2].sort());
// [ 1, 2, 3, 5, 8, 9 ]

Алгоритм, лежащий в основе этого встроенного метода sort(), реализуется по-разному в зависимости от того, какой браузер вы используете. Браузеры имеют разные JavaScript-движки, которые представляют собой способ выполнения кода JavaScript. Например, Chrome использует движок V8, а Mozilla Firefox использует SpiderMonkey. Mozilla использует сортировку слиянием, тогда как V8 использует Timsort (о котором мы не будем говорить в этой статье).

Как мы могли бы реализовать собственный способ сортировки списков без использования встроенного метода sort()? Вот что мы собираемся выяснить!

Давайте рассмотрим некоторые распространенные алгоритмы сортировки.

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

Наиболее распространенные алгоритмы сортировки

Глядя на время выполнения наихудшего случая, мы видим, что и пузырьковая сортировка, и сортировка выбором имеют время выполнения N^2. Это означает, что для каждого дополнительного элемента, добавляемого в набор сортируемых чисел, алгоритму требуется значительно больше времени для выполнения. Это означает, что пузырьковая сортировка и сортировка выбором будут плохими алгоритмами для использования на больших наборах данных. Однако, если вы работаете с меньшими наборами данных и знаете, что это останется небольшим набором данных, в использовании этих алгоритмов нет ничего плохого.

В общем, когда мы думаем об алгоритмах сортировки, мы обычно предполагаем наихудший сценарий n*log(n).

Если вы хотите узнать больше о временной сложности, перейдите к нашей статье Анализ сложности выполнения с помощью JavaScript. Но не забудьте вернуться!

Пузырьковая сортировка с помощью JavaScript

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

Пример пузырьковой сортировки. Источник: Википедия.

Пузырьковая сортировка — один из самых простых методов для решения с помощью JavaScript. Мы начнем со следующего кода:

function bubbleSort(arr) {
  // your code here
}
bubbleSort([3, 4, 9, 5, 1]);

Глядя на ввод, мы видим arr, что является сокращением от массива. arr будет массивом чисел. Как и во всех алгоритмах, которые мы реализуем в этой статье, наша цель — сортировать этот массив чисел от наименьшего к наибольшему.

Первый шаг, который мы собираемся сделать, это перебрать массив.

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {}
}
bubbleSort([3, 4, 9, 5, 1]);

Мы используем классический цикл for, чтобы получить доступ как к индексу, так и к элементу в каждой позиции массива.

Далее мы собираемся написать внутренний цикл for, который будет начинаться с индекса 0, вплоть до длины массива. Длина массива всегда смещается на 1 относительно индекса, потому что индексация массивов равна 0, поэтому -1 гарантирует, что наш код не будет повторяться там, где он не должен.

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {}
  }
}
bubbleSort([3, 4, 9, 5, 1]);

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

if (arr[j] > arr[j + 1]) {
  const lesser = arr[j + 1];
  arr[j + 1] = arr[j];
  arr[j] = lesser;
}

Оператор if гласит: if the current element at the current index is greater than the next one, где мы затем поменяем значения местами.

Примечание. Последний шаг не требует отдельного блока кода. Конечно, нам нужно return отсортированный массив. Проверьте полную реализацию ниже.

Реализация

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const lesser = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = lesser;
      }
    }
  }
  // return the sorted array
  return arr;
}
console.log(bubbleSort([3, 4, 9, 3, 1]));

Сортировка выбором с помощью JavaScript

Сортировка выбором — это алгоритм сортировки методом сравнения на месте со сложностью по времени n^2, что, как мы уже говорили выше, делает его неэффективным при работе с большими списками элементов. Он широко известен своей простотой и действительно дает прирост производительности по сравнению со сложными алгоритмами в определенных ситуациях.

Анимация сортировки выбором. Красный текущий мин. Желтый — отсортированный список. Синий — текущий элемент. Источник: Википедия.

Чтобы получить представление о том, как реализовать этот алгоритм, давайте немного подумаем об этом. Мы знаем, что нам нужно сравнивать элементы внутри массива, поэтому нам, вероятно, понадобится два цикла for.

Первым шагом алгоритма является запуск внешнего цикла for по всему массиву:

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {}
}

Мы также хотим объявить переменную indexMin и присвоить ее i, предполагая, что это наименьший элемент в массиве.

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let indexMin = i;
  }
}

Далее мы настроим еще один цикл for для проверки того, что indexMin действительно является наименьшим элементом в массиве, но if мы видим элемент, который меньше, мы собираемся записать его индекс, сохранив его в indexMin, как ниже:

for (let j = i + 1; j < arr.length; j++) {
  if (arr[j] < arr[indexMin]) {
    indexMin = j;
  }
}

Последний шаг нашего алгоритма — проверить, равно ли indexMin i. Помните, мы предполагали, что i — это наименьшее значение из приведенных выше. Если они не равны, их меняют местами.

if (indexMin !== i) {
  let lesser = arr[indexMin];
  arr[indexMin] = arr[i];
  arr[i] = lesser;
}

Вот и все. У нас есть реализация сортировки выбором. Но не забывайте — последним шагом будет return массив (arr). См. полную реализацию ниже.

Реализация

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let indexMin = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[indexMin]) {
        indexMin = j;
      }
    }
    if (indexMin !== i) {
      let lesser = arr[indexMin];
      arr[indexMin] = arr[i];
      arr[i] = lesser;
    }
  }
  return arr;
}
console.log(selectionSort([3, 4, 9, 3, 1]));

Сортировка слиянием с JavaScript

Сортировка слиянием — это алгоритм, изобретенный Джоном фон Нейманом, который был блестящим математиком, физиком, компьютерщиком, инженером и эрудитом. В отличие от двух описанных выше алгоритмов, сортировка слиянием является эффективным алгоритмом сортировки общего назначения. Он сортирует рекурсивно (мы немного рассмотрели рекурсию в этой статье о Фибоначчи), разделяя массив на несколько меньших массивов, которые сортируются, а затем объединяются. Мы будем использовать две отдельные функции, каждая из которых служит разным целям.

Короче говоря, сортировка слиянием:

  1. Делит несортированный список на n подсписков, каждый из которых содержит один элемент (список из одного элемента считается отсортированным).
  2. Повторно объединяет подсписки для создания новых отсортированных подсписков, пока не останется только один подсписок. Это будет отсортированный список.

Пример сортировки слиянием. Источник: Википедия.

Совет. Сортировка слиянием — это один из обязательных алгоритмов, которые рекомендует знать Гейл Лаакманн Макдауэлл, автор книги Cracking the Coding Interview.

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

Шаг 1: Слияние

Основная функция, mergeSort(), будет выполнять рекурсивные вызовы, поэтому вместо того, чтобы вводить этот алгоритм построчно, мы изучим каждую из функций по отдельности, так как код сложный и довольно трудный для понимания.

merge() немного проще, так что давайте сначала посмотрим на него.

Обратите внимание, что merge() принимает два параметра, left и right. left и right – это два отдельных отсортированных массива значений. По сути, цель нашей функции merge() — взять эти два отсортированных массива и объединить их вместе.

Возможно, вы уже думаете о том, как это сделать. Если вы подумали о том, чтобы объявить переменную и приравнять ее к пустому массиву, вы на правильном пути! Давайте посмотрим на функцию merge().

// merge()
function merge(left, right) {
  const results = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      results.push(left.shift());
    } else {
      results.push(right.shift());
    }
  }
  return [...results, ...left, ...right];
}

Немного изучите приведенный выше блок кода. Здесь не происходит ничего слишком сложного, и функция не содержит слишком много кода. Попробуем запустить. Сохраните код там, где вы сможете его запустить, и добавьте console.log(merge([3, 2, 1], [9, 2, 3])) после функции. Если вы запустите это, вы увидите, что два массива, left и right, были объединены, возвращая один массив: [ 3, 2, 1, 9, 2, 3 ].

Чтобы лучше понять, что делает наш код выше, эти ссылки могут быть вам полезны:

Шаг 2: сортировка слиянием

Пока мы реализовали одну часть нашего алгоритма. Пришло время завершить его, внедрив mergeSort().

После того, как вы потратите некоторое время на то, чтобы понять функцию merge(), взгляните на функцию ниже, mergeSort(). Здесь все будет запутанно.

// mergeSort()
function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  }
  const center = Math.floor(arr.length / 2);
  const left = arr.slice(0, center);
  const right = arr.slice(center);
  return merge(mergeSort(left), mergeSort(right));
}

Во-первых, давайте на самом деле протестируем наш код.

console.log(mergeSort([4, 3, 2, 1])) -> [ 1, 2, 3, 4 ]

Это работает, но что происходит?

Если мы немного замедлимся и подумаем об этом, мы увидим, что мы должны взять параметр arr, разделить его на два, а затем передать в функцию merge() (но только тогда, когда больше нечего делать). разделить).

Давайте посмотрим, что делают эти три переменные.

const center = Math.floor(arr.length / 2);
const left = arr.slice(0, center);
const right = arr.slice(center);
console.log(center, left, right);
// 2 [ 4, 3 ] [ 2, 1 ]
// 1 [ 4 ] [ 3 ]
// 1 [ 2 ] [ 1 ]

Итак, как мы сказали выше, наш код должен разделить массив пополам, пока он больше не может этого делать, в котором массив будет передан в функцию merge(). Поскольку в массиве всего 4 элемента, он будет разделен один раз посередине, а затем снова на left и right. У нас останутся [4, 3] и [2, 1], которые будут переданы в слияние как merge([4, 3], [2, 1]).

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

Реализация

function mergeSort(arr) {
  if (arr.length === 1) {
    return arr;
  }
  const center = Math.floor(arr.length / 2);
  const left = arr.slice(0, center);
  const right = arr.slice(center);
  return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
  const results = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      results.push(left.shift());
    } else {
      results.push(right.shift());
    }
  }
  return [...results, ...left, ...right];
}
console.log(mergeSort([3, 4, 9, 3, 1]));

Заключение

Это была длинная статья, и если вы дочитали до этого места, похлопайте себя по спине! Мы исследовали три разных алгоритма сортировки и написали их на JavaScript. Есть много других алгоритмов сортировки, которые вы, возможно, захотите проверить, например, быстрая сортировка, сортировка вставками и многие другие. Вы можете изучить их в других областях сети. Вы также можете подписаться на нашу рассылку справа, чтобы оставаться в курсе, когда мы пишем больше об алгоритмах в JavaScript.