Википедия

Сортировка пузырьком: различия между версиями

Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
→‎Псевдокод: дополнение
раньше было лучше
Строка 1:
'''Сортировка простыми обменами''', '''сортиро́вка пузырько́м''' ({{lang-en|bubble sort}}) — простой [[алгоритм сортировки]]. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: [[O большое|O]](''n''²); улучшенного (с уменьшением числа сравнений на 1 в каждом следующем внутреннем цикле): [[O большое|O]](''n''²/2).
 
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как [[шейкерная сортировка]], [[пирамидальная сортировка]] и [[быстрая сортировка]].
 
== Алгоритм ==
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован.<br> При каждом проходе алгоритма по внутреннему циклу, самый большой элемент массива помещается в конец массива и, в улучшенном алгоритме, в следующем внутреннем цикле число сравниваемых элементовстоящий уменьшаетсяне на 1, а самый маленький элемент массива перемещается к началу массива на одну позицию. Если поменять знак сравнения насвоём противоположныйместе, то«всплывает» надо каждомнужной проходепозиции покак внутреннему циклу очередной самый маленький элемент массива помещаетсяпузырёк в конец массиваводе, аотсюда самыйи большойназвание элемент массива перемещается к началу на одну позицию, в результате массив будет отсортирован в обратном порядкеалгоритма.
 
== [[Псевдокод (язык описания алгоритмов)|Псевдокод]] ==
DIM A[N] REM'''Вход:''' массив A[], состоящий из N элементов, с нумерацией от A[1] до A[N]▼
<source lang="qbasic">
sc := 0;
▲ DIM A[N] REM массив A[] из N элементов, с нумерацией от A[1] до A[N]
'''цикл пока''' N - sc > 0:
'''цикл для''' i = 2, ..., N-sc:
FOR J=1 TO N-1 STEP 1 REM Внешний цикл
'''если''' A[i] < A[i-1], '''то''':
FOR I+1 TO N-J STEP 1 REM Внутренний цикл
поменять местами A[i] и A[i-1];
IF A[I]>A[I+1] THEN SWAP A[I],A[I+1] REM Если выполняется условие, то обмен
sc := sc + 1;
NEXT I REM Конец тела внутреннего цикла
NEXT J REM Конец тела внешнего цикла
</source>
Обратите внимание, что количество повторов во внутреннем цикле уменьшается с каждым повторением внешнего цикла. Особенность данного алгоритма заключается в следующем: после первого завершения внутреннего цикла максимальный элемент массива всегда находится на N-ой позиции. При втором проходе, следующий по значению максимальный элемент будет находиться на N-1 месте. И так далее. Таким образом нет необходимости "обходить" весь массив от начала до конца каждый раз. Это ещё немного улучшает сортировку в части случаев.▼
 
▲Обратите внимание, что количество повторов во внутреннем цикле уменьшается с каждымкаждой повторениемитерацией внешнего цикла. Особенность данного алгоритма заключается в следующем: после первого завершения внутреннего цикла максимальный элемент массива всегда находится на N-ой позиции. При втором проходе, следующий по значению максимальный элемент будет находиться на N-1 месте. И так далее. Таким образом нет необходимости "обходить" весь массив от начала до конца каждый раз. Это ещё немного улучшает сортировку в части случаев.
Можно показать, что для сортировки требуется сделать не более N-1 проходов во внешнем цикле, поэтому в некоторых реализациях внешний цикл всегда выполняется ровно N-1 раз, и не отслеживается, были ли обмены на каждом проходе.▼
 
▲Можно показать, что для сортировки требуется сделать не более Nn -1 проходов1 воитераций внешнемвнешнего циклецикла, поэтому в некоторых реализациях внешний цикл всегда выполняется ровно Nn - 1 или n раз, и не отслеживается, были ли обмены или нет на каждомкаждой проходеитерации.
Иногда наименьшие элементы массива оказываются не на последних местах в массиве, тогда при последних проходах по внутреннему циклу обменов не происходит, что можно определить по состоянию флажка (F=0), в этих случаях сортировку можно окончить досрочно, что ещё немного улучшает сортировку в небольшой части случаев, но один проход без обменов по внутреннему циклу приходится делать. Так как число проверок на отсутствие обменов удваивает число проверок, а число случаев с досрочным окончанием невелико, то, чтобы не уменьшать быстродействие алгоритма, в большинстве случаев эту проверку можно не делать. Если нет стандартной функции обмена SWAP A[I],A[I+1], то для обмена двух элементов массива потребуется третья дополнительная ячейка памяти.
 
Алгоритм можно немного улучшить, сделав следующее:
Источник — https://ru.wikipedia.org/wiki/Сортировка_пузырьком