В этой статье мы узнаем о трех распространенных алгоритмах сортировки: пузырьковой сортировке, сортировке выбором и сортировке слиянием. Мы рассмотрим, для чего они полезны, а также как реализовать их в 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
Сортировка слиянием — это алгоритм, изобретенный Джоном фон Нейманом, который был блестящим математиком, физиком, компьютерщиком, инженером и эрудитом. В отличие от двух описанных выше алгоритмов, сортировка слиянием является эффективным алгоритмом сортировки общего назначения. Он сортирует рекурсивно (мы немного рассмотрели рекурсию в этой статье о Фибоначчи), разделяя массив на несколько меньших массивов, которые сортируются, а затем объединяются. Мы будем использовать две отдельные функции, каждая из которых служит разным целям.
Короче говоря, сортировка слиянием:
- Делит несортированный список на n подсписков, каждый из которых содержит один элемент (список из одного элемента считается отсортированным).
- Повторно объединяет подсписки для создания новых отсортированных подсписков, пока не останется только один подсписок. Это будет отсортированный список.
Пример сортировки слиянием. Источник: Википедия.
Совет. Сортировка слиянием — это один из обязательных алгоритмов, которые рекомендует знать Гейл Лаакманн Макдауэлл, автор книги 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.