Существует три общих метода сортировки массивов:
- Обмен
- Выбор (выборка)
- Вставка
Чтобы понять, как работают эти методы, представьте себе колоду игральных карт. Чтобы отсортировать карты методом обмена, разложите их на столе лицом вверх и меняйте местами карты, расположенные не по порядку, пока вся колода не будет упорядочена.
В методе выбораразложите карты на столе, выберите карту наименьшей значимости и положите ее в руку. Затем из оставшихся карт снова выберите карту наименьшей значимости и положите ее на ту, которая уже находится у вас в руке. Процесс повторяется до тех пор, пока в руке не окажутся все карты; по окончании процесса колода будет отсортирована.
Чтобы отсортировать колоду методом вставки, возьмите все карты в руку. Выкладывайте их по одной на стол, вставляя каждую следующую карту в соответствующую позицию. Когда все карты окажутся на столе, колода будет отсортирована.
Сортировка вставками
Сортировка вставками — простой алгоритм сортировки. Хотя этот алгоритм уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ:
- эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;
- эффективен на наборах данных, которые уже частично отсортированы;
- это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);
- может сортировать список по мере его получения;
Минусом -высокая сложность алгоритма: 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(n2-n)сравнений. Таким образом, это алгоритм порядка n2, из-за чего он считается слишком медленным для сортировки большого количества элементов. Несмотря на то, что количество сравнений в пузырьковой сортировке и сортировке посредством выбора одинаковое, в последней количество обменов в среднем случае намного меньше, чем в пузырьковой сортировке.
Реализация на 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 повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет
(n2-n)/2
сравнений, где n — количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n — 1 раз, а внутренний выполняется в среднем n/2 раз. Произведение этих величин и дает предыдущее выражение.
Обратите внимание на член n2 в формуле. Говорят, что пузырьковая сортировка является алгоритмом порядка n2, поскольку время ее выполнения пропорционально квадрату количества сортируемых элементов. Необходимо признать, что алгоритм порядка n2 не эффективен при большом количестве элементов, поскольку время выполнения растет экспоненциально в зависимости от количества сортируемых элементов.
В алгоритме пузырьковой сортировки количество обменов в лучшем случае равно нулю, если массив уже отсортирован. Однако в среднем и худшем случаях количество обменов также является величиной порядка n2.
Статьи к прочтению:
Автоматическая сортировка склада | Minecraft туториал 1.8+
Похожие статьи:
-
Сортировка методом простого выбора
Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т. д. int…
-
ЛАБОРАТОРНАЯ РАБОТА №4 Программирование алгоритмов с разветвляющейся структурой и с циклическими структурами. Массивы Цель и задача работы: научиться…