Если вы когда-либо проходили курс программирования, даже для начинающих, или если вы когда-либо пытались запрограммировать что-то более сложное, чем простая программа «Hello World», вам, скорее всего, приходилось думать об использовании как структур данных, так и работающих алгоритмов. по этим структурам данных.
Иногда бывает трудно понять, какой алгоритм сортировки лучше всего использовать для конкретного случая использования, когда вам нужно отсортировать данные в структуре данных. Это также может зависеть от того, с какой структурой данных вы работаете. Вот о чем эта статья. Поможем вам узнать, какие из наиболее распространенных алгоритмов сортировки лучше всего использовать в различных сценариях.
Среди наиболее распространенных алгоритмов сортировки:
- Вставка сортировки
- Пузырьковая сортировка
- Выбор Сортировка
- Сортировка слиянием
- Быстрая сортировка
Давайте рассмотрим каждый из них более подробно, чтобы увидеть различия между ними.
Сортировка вставкой
Сортировка вставкой - один из наиболее простых в реализации алгоритмов. Краткое описание того, как работает этот алгоритм, таково: Начните итерацию по каждому элементу в структуре данных (большую часть времени это массив или вектор), начиная со второго элемента в структуре данных, проверьте значение текущего элемента. элементу до него. Для каждого значения элемента в наборе данных, который предшествует текущему элементу, если его значение меньше, чем значение текущего элемента, переместите этот элемент на позицию вверх в наборе и продолжайте циклически проходить до тех пор, пока не появится элемент, значение которого не меньше, чем значение текущего элемента. И поместите в это место значение текущего элемента.
Наглядное представление о том, как работает этот алгоритм, можно найти здесь.
Лучшее время для использования этого алгоритма:
- Когда набор данных относительно невелик
- Когда элементы в наборе данных уже частично отсортированы
** Примечание. Некоторые более сложные алгоритмы, которые намного лучше подходят для сортировки больших наборов данных, будут использовать сортировку вставкой, если они разбивают набор данных на более мелкие наборы данных с помощью рекурсии. Они используют сортировку вставкой после того, как набор данных разбит на относительно небольшой набор данных
Сложность времени выполнения:
Наихудшая производительность: O (n²) - Итак, если в вашем массиве 100 элементов, в худшем случае этот алгоритм выполнит 10 000 сравнений. Это когда ваш набор данных сортируется полностью противоположно тому, как вы хотите сортировать данные.
Средняя эффективность наблюдения: O (n²) - Среднее значение не будет равно 10 000 сравнений, но оно будет выше, чем время O (n) или O (nlogn).
Лучшая производительность: O (n) - Лучшая производительность - это когда набор данных уже отсортирован, и требуется только итерация каждого элемента в массиве и одно сравнение для каждого элемента в наборе данных. .
Пример фрагмента кода (JavaScript):
function insertionSort(list) {
const len = list.length;
for (var i = 1; i < len; i++) {
var tmp = list[i];
for (var j = i - 1; j >= 0 && (list[j] > tmp); j--){
list[j + 1] = list[j];
}
list[j + 1] = tmp;
}
}Пузырьковая сортировка
Пузырьковая сортировка - еще один алгоритм, который относительно легко реализовать. Краткое описание того, как работает этот алгоритм, таково: Сравнивайте пары элементов за раз, меняя их местами, если первый элемент в паре больше, чем второй элемент в паре. Например, сравнивая пару элементов [8, 3], после сравнения пары порядок будет [3, 8]. Вы продолжаете делать это попарно по всему набору данных, пока не дойдете до последней пары элементов. Для каждой итерации набора данных будет выполнено n-x сравнений, где x - текущая итерация набора данных (индекс на основе 0).
Наглядное представление о том, как работает этот алгоритм, можно найти здесь.
Лучшее время для использования этого алгоритма:
- Когда набор данных относительно невелик
- Когда элементы в наборе данных уже частично отсортированы
* Примечание. Этот алгоритм не рекомендуется использовать для больших наборов данных. Особенно те, где элементы могут быть почти полностью отсортированы в обратном порядке.
Сложность времени выполнения:
Наихудшая производительность: O (n²) - Итак, если в вашем массиве 100 элементов, в худшем случае этот алгоритм выполнит 10 000 сравнений. Это когда ваш набор данных сортируется полностью противоположно тому, как вы хотите сортировать данные.
Средняя эффективность наблюдения: O (n²) - Среднее значение не будет равно 10 000 сравнений, но оно будет выше, чем время O (n) или O (nlogn).
Лучшая производительность: O (n) - Лучшая производительность - это когда набор данных уже отсортирован, и требуется только итерация каждого элемента в массиве и одно сравнение для каждого элемента в наборе данных. .
Пример фрагмента кода (JavaScript):
function bubbleSort(list) {
const length = list.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < (length - i - 1); j++) {
if (list[j] > list[j + 1]) {
var tmp = list[j];
list[j] = list[j + 1];
list[j + 1] = tmp;
}
}
}
}Сортировка выделения
Сортировка по выбору - еще один алгоритм, который относительно легко реализовать. Краткое описание того, как работает этот алгоритм, таково: Итерация по набору данных, начиная с первого элемента. Создайте ссылку на эту позицию в наборе данных, затем выполните итерацию по всем элементам в наборе и захватите наименьшее значение во всем списке, сохранив переменную, значение которой является наименьшим значением, наблюдаемым в этой итерации, и заменив ее текущим элемент. На каждой итерации индекс на 1 позицию выше в наборе, чем на предыдущей итерации. Когда индекс находится на последнем элементе в наборе данных, набор следует отсортировать.
Наглядное представление о том, как работает этот алгоритм, можно найти здесь.
Лучшее время для использования этого алгоритма:
- Когда набор данных относительно невелик
Примечание. Этот алгоритм не рекомендуется использовать для больших наборов данных. Во многих отношениях она очень похожа на сортировку вставкой, но сортировка вставкой по-прежнему будет более оптимальной, поскольку имеет возможность проводить меньше сравнений, чем сортировка по выбору. Однако сортировка по выбору имеет преимущество меньшего числа операций записи / обмена, чем сортировка вставкой.
Сложность времени выполнения:
Наихудший результат: O (n²) - наихудший случай совпадает как с худшим, так и с лучшим случаем. Этому алгоритму все равно нужно будет выполнить O (n²) сравнений, чтобы убедиться, что все в порядке. Это один из недостатков этого конкретного алгоритма.
Средняя производительность: O (n²) - Среднее значение совпадает как с худшим, так и с лучшим случаем. Этому алгоритму все равно нужно будет выполнить O (n²) сравнений, чтобы убедиться, что все в порядке. Это один из недостатков этого конкретного алгоритма.
Лучшая производительность: O (n²) - Лучшая производительность такая же, как и в худшем, и в среднем случае. Этому алгоритму все равно нужно будет выполнить O (n²) сравнений, чтобы убедиться, что все в порядке. Это один из недостатков этого конкретного алгоритма.
Пример фрагмента кода (JavaScript):
function selectionSort(list) {
const length = list.length;
for (var i = 0; i < length - 1; i++) {
var min = i;
for (var j = i + 1; j < length; j++) {
if (list[j] < list[min]) {
min = j;
}
}
if (min != i) {
//Swap the numbers
var tmp = list[i];
list[i] = list[min];
list[min] = tmp;
}
}
}Сортировка слиянием
Сортировка слиянием - это более сложный алгоритм, который не так просто реализовать, как описанные выше алгоритмы. Краткое описание того, как работает этот алгоритм, таково: Возьмите весь список и продолжайте разбивать его пополам, пока он не сократится до наименьшего возможного списка, по одному элементу в каждом списке. Затем сравните его со списком, примыкающим к нему, и отсортируйте элементы в этих списках, а затем объедините соседние списки и повторите повторение для следующего набора списков. Продолжайте делать это, пока список не будет отсортирован. Это один из алгоритмов сортировки, который обычно использует рекурсию и решает более серьезную проблему, разбивая ее на более мелкие подзадачи, известные как алгоритмы «разделяй и властвуй».
Наглядное представление о том, как работает этот алгоритм, можно найти здесь.
Лучшее время для использования этого алгоритма:
- Большие наборы данных
- Когда нет ограничений памяти или хранилища, поскольку наиболее распространенные реализации сортировки слиянием используют вторичный список, используя тот же объем пространства, что и исходный список, чтобы помочь с сортировкой.
- Когда к элементам в наборе данных можно получить доступ последовательно
Сложность времени выполнения:
Наихудший случай: O (nlogn) - наихудший случай совпадает как с худшим, так и с лучшим случаем.
Средняя производительность: O (nlogn) - Среднее значение совпадает как с худшим, так и с лучшим случаем.
Лучшая производительность: O (nlogn) - Лучшая производительность такая же, как и в худшем, и в среднем случае.
Пример фрагмента кода (JavaScript)
function mergeSort(arr) {
if (arr.length < 2) {
return arr;
}
var mid = Math.floor(arr.length / 2);
var subLeft = mergeSort(arr.slice(0, mid));
var subRight = mergeSort(arr.slice(mid));
return merge(subLeft, subRight);
}
function merge(node1, node2) {
var result = [];
while (node1.length > 0 && node2.length > 0) { result.push(node1[0] < node2[0]? node1.shift() : node2.shift()); return result.concat(node1.length? node1 : node2);
}
Быстрая сортировка
Быстрая сортировка - это более сложный алгоритм, который не так просто реализовать, как более простые алгоритмы, описанные в начале этой статьи. Это похоже на сортировку слиянием, поскольку в ней используется подход «разделяй и властвуй». Краткое описание того, как работает этот алгоритм, выглядит следующим образом: Выберите элемент из набора данных, называемый точкой поворота, и это точка, в которой набор данных разделяется. Переместите все элементы в наборе данных, которые меньше значения поворота, которое должно быть перед поворотом. Рекурсивно примените одни и те же шаги для каждого из разделов, созданных на предыдущем шаге.
Наглядное представление о том, как работает этот алгоритм, можно найти здесь.
Лучшее время для использования этого алгоритма:
- Большие наборы данных
- Когда порядок равных элементов не важен. Быстрая сортировка не является стабильным алгоритмом, а это означает, что после того, как набор данных упорядочен, элементы, значения которых равны, не гарантируют, что они будут в том же порядке, что и исходный набор данных.
Сложность времени выполнения:
Худший случай производительности: O (n²) - Для Quicksort сложность времени выполнения n² является редкостью. Так что это не должно сильно беспокоить.
Средняя эффективность: O (nlogn) - Среднее значение такое же, как и в лучшем случае.
Лучшая производительность: O (nlogn) - Лучшая производительность такая же, как и средняя.
Если вы нашли эту статью полезной, подпишитесь на эту публикацию, если вы хотите увидеть больше похожих!
