Существует три общих метода сортировки массивов:
- Обмен
- Выбор (выборка)
- Вставка
Чтобы понять, как работают эти методы, представьте себе колоду игральных карт. Чтобы отсортировать карты методом обмена, разложите их на столе лицом вверх и меняйте местами карты, расположенные не по порядку, пока вся колода не будет упорядочена.
В методе выбора разложите карты на столе, выберите карту наименьшей значимости и положите ее в руку. Затем из оставшихся карт снова выберите карту наименьшей значимости и положите ее на ту, которая уже находится у вас в руке. Процесс повторяется до тех пор, пока в руке не окажутся все карты; по окончании процесса колода будет отсортирована.
Чтобы отсортировать колоду методом вставки, возьмите все карты в руку. Выкладывайте их по одной на стол, вставляя каждую следующую карту в соответствующую позицию. Когда все карты окажутся на столе, колода будет отсортирована.
Сортировка вставками
Сортировка вставками — простой алгоритм сортировки. Хотя этот алгоритм уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ:
· эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
· эффективен на наборах данных, которые уже частично отсортированы;
· это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
· может сортировать список по мере его получения;
Минусом -высокая сложность алгоритма: O(n ²)
Вообще говоря, в худших случаях сортировка вставками настолько же плоха, как и пузырьковая сортировка и сортировка посредством выбора, а в среднем она лишь немного лучше.
Описание
На каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.
Анализ Алгоритма
Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим — массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных — θ(n²).
Реализация на java
public void addingSort() {
for (Node cur = first.next; cur!= null; cur = cur.next) {
Node n = cur.prev;
Object val = cur.value;
for (; n!= null; n = n.prev) {
if (((Comparable) n.value).compareTo(val) > 0) {
n.next.value = n.value;
} else {
break;
}
}
if (n!= null) {
n.next.value = val;
} else {
first.value = val;
}
}
}
Сначала он сортирует два первых элемента. Затем алгоритм вставляет третий элемент в соответствующую порядку позицию по отношению к первым двум элементам. После этого он вставляет четвертый элемент в список из трех элементов. Этот процесс повторяется до тех пор, пока не будут вставлены все элементы. Например, при сортировке массива dcab каждый проход алгоритма будет выглядеть следующим образом:
Начало d c a b
Проход 1 c d a b
Проход 2 a c d b
Проход 3 a b c d
Сортировка выбором
Описание
При сортировке из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихся n - 1 элементов снова выбирается элемент с наименьшим ключом и обменивается со вторым элементом, и т.д. Эти обмены продолжаются до двух последних элементов. Например, если применить метод выбора к массиву dcab, каждый проход будет выглядеть так:
Начало d c a bПроход 1 a c d bПроход 2 a b d cПроход 3 a b c dАнализ
К сожалению, как и в пузырьковой сортировке, внешний цикл выполняется n - 1 раз, а внутренний — в среднем n /2 раз. Следовательно, сортировка посредством выбора требует 1/2(n 2- n) сравнений. Таким образом, это алгоритм порядка n 2, из-за чего он считается слишком медленным для сортировки большого количества элементов. Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировке посредством выбора одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке.
Реализация на java
public void SelectSort() {
Object c;
for (Node a = first; a!= last; a = a.next) {
Node min = last;
for (Node b = a; b!= last; b = b.next) {
if (((Comparable) b.val).compareTo(min.val) < 0) {
min = b;
}
}
c = a.val;
a.val = min.val;
min.val = c;
}
}
Сортировка Обменом
Самый известный алгоритм — пузырьковая сортировка. Его популярность объясняется интересным названием и простотой самого алгоритма. Тем не менее, в общем случае это один из самых худших алгоритмов сортировки.
Пузырьковая сортировка относится к классу обменных сортировок, т.е. к классу сортировок методом обмена. Ее алгоритм содержит повторяющиеся сравнения (т.е. многократные сравнения одних и тех же элементов) и, при необходимости, обмен соседних элементов. Элементы ведут себя подобно пузырькам воздуха в воде — каждый из них поднимается на свой уровень.
Чтобы наглядно показать, как работает пузырьковая сортировка, допустим, что исходный массив содержит элементы dcab. Ниже показано состояние массива после каждого прохода:
Начало d c a b
Проход 1 a d c b
Проход 2 a b d c
Проход 3 a b c d
При анализе любого алгоритма сортировки полезно знать, сколько операций сравнения и обмена будет выполнено в лучшем, среднем и худшем случаях. Поскольку характеристики выполняемого кода зависят от таких факторов, как оптимизация, производимая компилятором, различия между процессорами и особенности реализации, мы не будем пытаться получить точные значения этих параметров. Вместо этого сконцентрируем свое внимание на общей эффективности каждого алгоритма.
В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет
(n 2- n)/2
сравнений, где n — количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n - 1 раз, а внутренний выполняется в среднем n /2 раз. Произведение этих величин и дает предыдущее выражение.
Обратите внимание на член n 2 в формуле. Говорят, что пузырьковая сортировка является алгоритмом порядка n 2, поскольку время ее выполнения пропорционально квадрату количества сортируемых элементов. Необходимо признать, что алгоритм порядка n 2 не эффективен при большом количестве элементов, поскольку время выполнения растет экспоненциально в зависимости от количества сортируемых элементов.
В алгоритме пузырьковой сортировки количество обменов в лучшем случае равно нулю, если массив уже отсортирован. Однако в среднем и худшем случаях количество обменов также является величиной порядка n 2.
