 |
|
Пример работы алгоритма
Сортировка пузырьком
Сортировка простыми обменами, сортиро́вка пузырько́м— простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка.
Алгоритм
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Псевдокод
Псевдокод улучшенного алгоритма с почти вдвое уменьшенным числом проходов.
На входе: массив A[N], состоящий из N элементов, с нумерацией от A[1] до A[N]
ЦИКЛ ДЛЯ J=1 ДО N-1 ШАГ 1 FOR J=1 TO N-1 STEP 1
ЦИКЛ ДЛЯ I=1 ДО N-J ШАГ 1 FOR I=1 TO N-J STEP 1
ЕСЛИ A[I]>A[I+1] ТО ОБМЕН A[I],A[I+1] IF A[I]>A[I+1] THEN SWAP A[I],A[I+1]
СЛЕДУЮЩЕЕ I NEXT I
СЛЕДУЮЩЕЕ J NEXT J
В улучшенном алгоритме количество повторов во внутреннем цикле уменьшается на 1 с каждой итерацией внешнего цикла.
Если нет функции обмена (SWAP A[I],A[I+1]), то её можно заменить тремя операторами присваивания:
TEMP=A[I]
A[I]=A[I+1]
A[I+1]=TEMP
Cложность: O(n·n), не уменьшается.
Особенность данного алгоритма заключается в следующем: после первого завершения внутреннего цикла максимальный элемент массива всегда находится на N-ой позиции. При втором проходе, следующий по значению максимальный элемент находится на N-1 месте. И так далее. Таким образом, на каждом следующем проходе число обрабатываемых элементов уменьшается на 1 и нет необходимости «обходить» весь массив от начала до конца каждый раз.
Пример работы алгоритма
Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
Первый проход:
(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.
(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 5 > 4
(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как 5 > 2
(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.
Второй проход:
(1 4 2 5 8) (1 4 2 5 8)
(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как 4 > 2
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.
Третий проход:
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
Теперь массив отсортирован и алгоритм может быть завершён.
Задание.
При решении заданий необходимо записывать массив и пошаговые значения i и j. Например, рассмотренный выше пример оформляется следующим образом:
I=1
J=1
I=…
J=… и т.д.
.
1. Требуется отсортировать массив (12, 5, 3, 7, 10, 1, 3, 23, 15, 1, 4). На каждом шаге необходимо указать значения i и j.
2. Измените алгоритм таким образом, чтобы самый тяжелый элемент «падал на дно», а не самый легкий «всплывал».
3. Отсортируйте массив (12, 5, 3, 7, 10, 1, 3, 23, 15, 1, 4) алгоритмом, составленным в п.2.
Сортировка выбором
Алгоритм сортировки. На массиве из n элементов имеет время выполнения в худшем, среднем и лучшем случае Θ(n2), предполагая что сравнения делаются за постоянное время.
Шаги алгоритма:
1. находим номер минимального значения в текущем списке
2. производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции)
3. теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы
Пример:
template <class Item>void selection(Item a[], int len) { /* внешний цикл. i – позиция первого неотсортированного элемента на данной итерации */ for (int i = 0; i < len - 1; i++) { int min = i; /* min – позиция минимального элемента */ /* внутренний цикл. если найден элемент строго меньший текущего минимального, записываем его индекс как минимальный */ for(int j = i + 1; j < len; j++) { if(a[j] < a[min]) min = j; } if(min != i) /* минимальный элемент не является первым неотсортированным, обмен нужен */ exch(a[i], a[min]); }}
Задание.
1. Отсортировать массив (45, 12, 0, 34, 3, 67, 15, 40, 23) с помощью сортировки выбором.