Сортировка пузырьком — различия между версиями
Warrior (обсуждение | вклад) (→Псевдокод) |
Warrior (обсуждение | вклад) (→Оптимизация) |
||
| Строка 13: | Строка 13: | ||
== Оптимизация == | == Оптимизация == | ||
| − | * | + | * Можно заметить, что после <tex> i </tex>-ой итерации внешнего цикла <tex> i </tex> последних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, внутренний цикл можно выполнять не до <tex> n - 2 </tex>, а до <tex> n - i - 2 </tex>. |
| − | * | + | * Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не <tex> n - 1 </tex> раз, а до тех пор, пока во внутреннем цикле происходят обмены. |
| − | + | ||
| − | + | Тогда сортировка примет такой вид: | |
| − | + | BubbleSort(A) | |
| − | + | i = 0; | |
| − | + | t = true; | |
| − | + | while t == true | |
| − | + | t = false; | |
| − | + | for j = 0 to n - i - 2 | |
| + | if A[j] > A[j + 1] | ||
| + | swap(A[j], A[j + 1]); | ||
| + | t = true; | ||
| + | i = i + 1; | ||
== Пример работы алгоритма == | == Пример работы алгоритма == | ||
Версия 19:15, 1 июня 2012
Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Сложность алгоритма:
Алгоритм
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Псевдокод
Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив , состоящий из элементов.
BubbleSort(A)
for i = 0 to n - 2
for j = 0 to n - 2
if A[j] > A[j + 1]
swap(A[j], A[j + 1]);
Оптимизация
- Можно заметить, что после -ой итерации внешнего цикла последних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, внутренний цикл можно выполнять не до , а до .
- Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не раз, а до тех пор, пока во внутреннем цикле происходят обмены.
Тогда сортировка примет такой вид:
BubbleSort(A)
i = 0;
t = true;
while t == true
t = false;
for j = 0 to n - i - 2
if A[j] > A[j + 1]
swap(A[j], A[j + 1]);
t = true;
i = i + 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 |
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще 2 прохода, на которых ничего не изменится.
См. также
- Сортировка выбором
- Сортировка вставками
- Сортировка кучей
- Сортировка слиянием
- Быстрая сортировка
- Сортировка подсчетом
