С тех пор, как я впервые услышал об алгоритмах сортировки, они всегда были синонимом большого удовольствия!
Организация элементов из списка — это то, что очень часто требуется в нашей повседневной жизни, чаще всего порядок очень прямолинейный, например, числовой или с соблюдением какого-либо флага приоритета. Тем не менее, современные разработчики очень абстрагируются от своих реализаций.
Хотя проблема довольно проста, решения не очень прямолинейны, говоря от себя, я часто вижу, как пересматриваю самые распространенные алгоритмы. Несколько месяцев назад я решил реализовать на JS 4 самых популярных алгоритма сортировки:
- сортировка вставками;
- пузырьковая сортировка;
- Сортировка слиянием;
- Быстрая сортировка.
Надеюсь, что эта статья поможет вам прояснить их концепцию и предоставить вам простую реализацию.
Сортировка вставками
function insertionSort(arrayToSort) { for (let i = 1; i < arrayToSort.length; i++) { let j = i; while (j > 0 && arrayToSort[j-1] > arrayToSort[j]) { swap(arrayToSort, j-1, j); j--; } } return arrayToSort; }
Сортировка вставками работает, беря элементы из списка один за другим, а затем сравнивая значения со значениями, уже посещенными в текущем списке. К концу n итераций мы гарантируем, что n элементы отсортированы.
* В худшем случае O(n^{2}) сравнений
* В лучшем случае O(n) сравнений
Пузырьковая сортировка
function bubbleSort(arrayToSort) { for (let i = 0; i < arrayToSort.length; i++) { for (let j = 0; j < (arrayToSort.length - i - 1); j++) { if (arrayToSort[j] > arrayToSort[j+1]) { swap(arrayToSort, j, j+1); } } } return arrayToSort; }
Пузырьковая сортировка довольно проста и неэффективна. Эффективность будет зависеть от списка, заданного в качестве входных данных, но в большинстве случаев эффективен только при использовании в почти отсортированном/отсортированном списке.
* В худшем случае O(n^{2}) сравнений
* В лучшем случае O(n^{2}) сравнений — может быть O(n), если добавить дополнительную проверку, чтобы убедиться, что массив уже отсортирован
Сортировка слиянием
function mergeSort(arrayToSort) { if (arrayToSort.length === 1) { return arrayToSort; } const middle = Math.floor(arrayToSort.length / 2); const left = arrayToSort.slice(0, middle); const right = arrayToSort.slice(middle); return merge(mergeSort(left), mergeSort(right)); } function merge(left, right) { let result = []; while (left.length && right.length) { if (left[0] > right[0]) { result.push(right.shift()); } else { result.push(left.shift()); } } while (left.length) { result.push(left.shift()); } while (right.length){ result.push(right.shift()); } return result; }
Сортировка слиянием использует преимущества объединения уже отсортированных списков. Реализация начинается с разбиения входного списка на два отдельных списка и рекурсивного разбиения на более мелкие части, сосредотачиваясь на сохранении организованности разделенных списков и сохранении левой стороны «меньше», чем правой.
* В худшем случае O(n log n) сравнений
* В лучшем случае O(n log n) сравнений
Быстрая сортировка
function quickSort(arrayToSort) { if (arrayToSort.length <= 1) { return arrayToSort; } let left = []; let right = []; let result = []; let pivot = arrayToSort.shift(); for (let i=0; i < arrayToSort.length; i++) { if (arrayToSort[i] > pivot) { right.push(arrayToSort[i]); } else { left.push(arrayToSort[i]); } } return result.concat(quickSort(left), pivot, quickSort(right)); }
Быстрая сортировка отлично подходит для больших списков. Использует подход «разделяй и властвуй». Алгоритм выбирает опорную точку и из этой опорной точки список разбивается на более мелкие списки. Имейте в виду, что выбор хорошего разворота (разворот должен быть как можно ближе к медиане, в текущей реализации я выбираю первый элемент) может значительно повысить эффективность. Выполнение этого алгоритма может быть легко распределено с использованием многопоточного подхода.
* В худшем случае O(n log n) сравнений
* В лучшем случае O(n log n) сравнений
Я использовал функцию подкачки в некоторых алгоритмах. Эта функция должна быть примерно такой:
function swap(arrayToSwap, firstIndex, secondIndex) { const temp = arrayToSwap[firstIndex]; arrayToSwap[firstIndex] = arrayToSwap[secondIndex]; arrayToSwap[secondIndex] = temp; }
Существует много дополнительной информации об алгоритмах сортировки, не стесняйтесь исследовать. Я также создал общедоступный репозиторий GitHub с этим кодом:
https://github.com/JMGomes/SortingAlgorithms/
В этом репозитории вы обнаружите, что я заменил обычный оператор сравнения (значение1 › значение2) абстрактной функцией с именем customCompare(). Это позволяет пользователям использовать более сложный оператор сравнения, например. чтение свойства объекта.
Используя этот репозиторий, вы также можете передавать свои собственные входные массивы и сравнивать себя по времени выполнения каждого алгоритма. Это самая забавная часть, имхо.
Спасибо