В этом посте мы рассмотрим пару алгоритмов сортировки массивов в JavaScript и покажем их базовую реализацию. Оставайтесь с нами во второй части, где мы рассмотрим варианты оптимизации для каждого из них. (Этот пост также скоро будет расширен, чтобы включить остальные наиболее распространенные алгоритмы сортировки: сортировка вставками, сортировка слиянием, быстрая сортировка и сортировка по основанию)
Пузырьковая сортировка
Пузырьковая сортировка — худший алгоритм сортировки, который только можно придумать. Есть люди, активно пытающиеся исключить его из учебных программ по информатике из-за его сложности O(n²). Хотя, возможно, нет необходимости показывать кому-то, как сделать что-то наихудшим способом, когда есть гораздо более эффективные альтернативы, я считаю, что это все же хороший образовательный инструмент для обучения новичков работе алгоритмов из-за его простоты. Кроме того, если список уже в основном отсортирован, пузырьковая сортировка не такая уж плохая идея.
Название происходит от больших значений (или меньших, в зависимости от того, как вы сортируете), которые «всплывают» до конца массива. Как это работает, вы перебираете массив и меняете местами каждые два соседних элемента, если они не отсортированы. Цикл, выполняющий такую задачу, вложен во внешний цикл, также равный количеству элементов, поэтому выполняется обход массива n раз, в результате чего при каждом запуске наибольшие числа будут сдвигаться вверх ближе к концу. . так:
[2,5, 4,3,1]
Сначала мы смотрим на 2 и 5, которые уже отсортированы. Затем мы переходим к 5 и 4, которых нет, поэтому мы меняем их местами.
[2,4,5,3,1]
затем мы смотрим на 5 и 3, которые не отсортированы, поэтому они меняются местами.
[2,4,3,5,1]
наконец, мы смотрим на 5 и 1 и меняем их местами.
[2,4,3,1,5]
Внутренний цикл выполнен, поэтому мы возвращаемся ко второй итерации внешнего цикла, в результате чего 4 будет слева от 5;
[2,3,1,4,5]
Как только мы запустим внутренний цикл 5 раз, массив будет отсортирован.
[1,2,3,4,5]
Вот как это выглядит в коде:
function bubbleSort(array) { let j = 0; while (j <= array.length) { for (i = 0; i < array.length; i++) { if (array[i] > array[i + 1]) { let hold = array[i]; array[i] = array[i + 1]; array[i + 1] = hold; } } j++; } return array; };
Сортировка выбором
Сортировка выбором чем-то похожа на сортировку пузырьком. Вместо того, чтобы перемещать большие элементы в конец массива, мы перемещаем меньшие элементы влево от массива. Реализация несколько другая. Для каждой итерации мы ищем наименьший текущий элемент и перемещаем его в соответствующую позицию. Однако нам также нужен вложенный цикл внутри внешнего цикла. Мы начнем со сравнения первых двух элементов и сохраним наименьший из двух, затем мы сравним сохраненный элемент с каждым другим значением, и если мы обнаружим, что есть меньший элемент, мы заменим его текущим сохраненным значением. В конце прохода мы меняем местами наименьший найденный элемент с элементом в первой позиции.
Теперь для второй итерации мы начинаем со второй позиции, так как мы уже отсортировали элемент в первую позицию, третий проход начнется с третьего элемента и так далее и тому подобное. Итак, резюмируем: мы сохраняем первый элемент как наименьшее значение, которое вы видели, сравнивайте указанное значение со следующим элементом, пока не найдете меньшее и не достигнете конца массива. Мы сохраняем индекс, а не само значение, поэтому мы можем поменять его местами с крайним левым элементом, если значение с индексом 0 еще не было наименьшим. Повторите процесс, начиная с несортированного индекса, убедитесь, что вы не начинаете с любого места в уже отсортированном подмассиве, иначе вы всегда найдете один и тот же минимум. Для этого инициализация внутреннего цикла может быть j = i + 1;
Давайте посмотрим на тот же несортированный массив, который мы использовали для объяснения пузырьковой сортировки, и пройдемся по нему, используя сортировку выбором:
[2,5,4,3,1]
Мы устанавливаем наименьшее значение = 2, так как это первое число, которое мы видим. Затем мы сравниваем его со следующим элементом. 5 определенно не меньше, ни 4, ни 3, но в конце концов мы находим меньший, 1. Поэтому мы меняем их местами.
[1,5,4,3,2]
Теперь для следующей итерации мы начинаем со второй позиции индекса и устанавливаем 5 как наименьшее число, так как это первое, с которым мы столкнулись. При сравнении с остальными числами мы обнаруживаем, что два на самом деле наименьшее число, поэтому мы меняем его на 5.
[1,2,4,3,5]
Теперь мы устанавливаем 4 наименьшее число, так как мы уже отсортировали первые два элемента. Вот 3 — наименьший в несортированном наборе, поэтому мы меняем его местами.
[1,2,3,4,5]
Ух ты! мы закончили раньше! несмотря на то, что осталась еще одна итерация, алгоритм обнаруживает, что менять местами нечего, и возвращает наш отсортированный массив.
Вот как выглядит код:
function selectionSort(){ for (let i = 0; i < array.length; i++){ let lowest = i; for(let j = i + 1; j < array.length; j++){ if(array[j] < array[lowest]){ lowest = j; } } if (i !== lowest){ let hold = array[i]; let array[i] = array[lowest]; let array[lowest] = hold } } return array; }