Просмотр кода страницы Сортировка пузырьком

{{Алгоритм
| предназначение = [[Алгоритм сортировки]]
| изображение = Bubble-sort-example-300px.gif
| подпись = Визуализация сортировки массива чисел алгоритмом сортировки пузырьком
| данные = [[Массив (программирование)|Массив]]
| время = <math>O(n^2)</math>
| лучшее-время = <math>O(n)</math>
| среднее-время = <math>O(n^2)</math>
| память = <math>O(1)</math>
}}
'''Сортировка пузырько́м''' ({{lang-en|bubble sort}}), '''сортиро́вка простыми обменами''', метод сортировки обменами — один из [[алгоритм сортировки|алгоритмов сортировки]]. По сравнению с другими алгоритмами считается простейшим для понимания и реализации. Эффективен для массивов небольшого размера. <math>n</math> — размер массива, количество элементов массива. [[Вычислительная сложность|Сложность]] алгоритма: [[O большое|<math>O</math>]]<math>(n^2)</math>.

Алгоритм считается учебным, вне учебной литературы не применяется (на практике применяются более эффективные (совершенные) алгоритмы). Лежит в основе некоторых более эффективных алгоритмов, например, алгоритма [[шейкерная сортировка|шейкерной сортировки]], алгоритма [[пирамидальная сортировка|пирамидальной сортировки]] и алгоритма [[быстрая сортировка|быстрой сортировки]].

== Алгоритм ==
Выполняется некоторое количество проходов по массиву — начиная от начала массива, перебираются пары соседних элементов массива. Если 1-й элемент пары больше 2-го, элементы переставляются (выполняется обмен).

Пары элементов массива перебираются (проходы по массиву повторяются) либо <math>(n-1)</math> раз, либо до тех пор, пока на очередном проходе не обнаружится, что более не требуется выполнять перестановки (обмены) (массив отсортирован).

При каждом проходе алгоритма по внутреннему циклу очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива (как бы «всплывает» до нужной позиции, как пузырёк в воде — откуда и название алгоритма).

== Реализация ==
Сложность: <math>O(n^2)</math>.

Для наихудшего случая верно следующее.
* Элементы массива упорядочены по убыванию (например, «3 2 1»).
* Количество сравнений, выполняемых в теле цикла, равно <math>(n-1) \cdot \frac n 2</math>.
* Количество сравнений, выполняемых в заголовках циклов, равно <math>(n-1) \cdot \frac n 2</math>.
* Суммарное количество сравнений равно <math>(n-1) \cdot n</math>.
* Количество присваиваний в заголовках циклов равно <math>(n-1) \cdot \frac n 2</math>.
* Количество перестановок равно <math>(n-1) \cdot \frac n 2</math> (что в <math>\frac n 2</math> раз больше, чем при [[Сортировка выбором|сортировке выбором]]).

Для наилучшего случая верно следующее.
* Элементы массива упорядочены по возрастанию (например, «1 2 3»).
* Количество сравнений, выполняемых в теле цикла, равно <math>(n-1) \cdot \frac n 2</math>.
* Количество сравнений, выполняемых в заголовках циклов, равно <math>(n-1) \cdot \frac n 2</math>.
* Суммарное количество сравнений равно <math>(n-1) \cdot n</math>.
* Количество перестановок равно числу 0.

Особенность алгоритма. После 1-го прохода (завершения внутреннего цикла) максимальный элемент массива находится в позиции номер <math>(n-1)</math>. После 2-го прохода следующий по значению максимальный элемент находится в позиции номер <math>(n-2)</math>. И так далее. Для каждого следующего прохода по сравнению с текущим проходом количество обрабатываемых элементов меньше на единицу. Нет необходимости каждый проход перебирать все пары элементов («обходить» весь массив) от начала массива к концу массива.

Если <math>n=1</math> (массив содержит один элемент), то не требуется сортировать массив. Если <math>n>1</math>, для сортировки массива требуется выполнить не более <math>(n-1)</math> итераций внешнего цикла. Некоторые реализации выполняют тело внешнего цикла <math>(n-1)</math> раз и не учитывают (не отслеживают) информацию о том, были ли или не были перестановки на каждой итерации цикла.

Если на вход подаётся частично отсортированный массив, то можно уменьшить количество проходов по массиву — ввести индикатор произошедших перестановок (флажок F). Перед каждым проходом по внутреннему циклу флажок F сбрасывается в 0, а после перестановки — устанавливается в 1. Если после выполнения внутреннего цикла флажок F равен 0, то при выполнении внутреннего цикла перестановок не было; то есть, массив отсортирован и можно досрочно выйти из программы сортировки.

Псевдокод улучшенного алгоритма — алгоритма с проверкой, были ли перестановки во внутреннем цикле.

На входе: массив <math>A[n]</math> — массив, содержащий <math>n</math> элементов. 1-й элемент обозначен как <math>A[0]</math>, последний — как <math>A[n-1]</math>.
<source lang="fortran">
 ЦИКЛ ДЛЯ J=1 ДО n-1 ШАГ 1                       FOR J=1 TO n-1 STEP 1
   F=0                                             F=0
   ЦИКЛ ДЛЯ I=0 ДО n-1-J ШАГ 1                     FOR I=0 TO n-1-J STEP 1
     ЕСЛИ A[I] > A[I+1] ТО ОБМЕН A[I],A[I+1]:F=1     IF A[I]>A[I+1] THEN SWAP A[I],A[I+1]:F=1
   СЛЕДУЮЩЕЕ I                                     NEXT I
   ЕСЛИ F=0 ТО ВЫХОД ИЗ ЦИКЛА                      IF F=0 THEN EXIT FOR
 СЛЕДУЮЩЕЕ J                                     NEXT J
</source>
Чтобы досрочно завершить программу сортировки, требуется выполнить один (избыточный) проход без обменов.

Для наихудшего (не улучшаемого) случая верно следующее.
* Количество сравнений, выполняемых в теле цикла, равно <math>(n-1) \cdot \frac n 2</math>.
* Количество сравнений, выполняемых в заголовках циклов, равно <math>(n-1) \cdot \frac n 2</math>.
* Суммарное количество сравнений равно <math>(n-1) \cdot n</math>.
* Количество присваиваний в заголовках циклов равно <math>(n-1) \cdot \frac n 2</math>.
* Количество перестановок равно <math>(n-1) \cdot \frac n 2</math>.

Для наилучшего случая верно следующее.
* Количество сравнений, выполняемых в теле цикла, равно <math>(n-1)</math>.
* Количество сравнений, выполняемых в заголовках циклов, равно <math>(n-1)</math>.
* Суммарное количество сравнений равно <math>2 \cdot (n-1)</math>.
* Количество перестановок (обменов) равно числу 0.

На [[Программно-аппаратный комплекс|программно-аппаратном комплексе]], выполняющем сравнение примерно 3,4 мкс и выполняющем перестановку примерно 2,3 мкс, время сортировки 10 000 коротких целых чисел реализацией алгоритма [[Сортировка выбором|сортировки выбором]] составило примерно 40 с, ещё более улучшенной сортировкой пузырьком — примерно 30 с, а [[Быстрая сортировка|быстрой сортировкой]] — примерно 0,027 с.

<math>O(n \cdot n)</math> больше, чем <math>O(n \cdot \log n)</math> у [[Сортировка слиянием|сортировки слиянием]]. Но при малых <math>n</math> разница не очень большая, а программный код сравнительно прост. Поэтому вполне допустимо применение сортировки пузырьком для множества задач с массивами малой размерности на простаивающих и малозагруженных машинах.

Если во внутреннем цикле просматривать массив не от начала к концу, а поочерёдно то от начала к концу, то от конца к началу, то получится алгоритм, называемый алгоритмом [[Сортировка перемешиванием|сортировки перемешиванием (шейкерной сортировки)]]. Сложность полученного алгоритма равна <math>O(n \cdot n)</math>, не меньше сложности исходного алгоритма.

При сортировке пузырьком при каждом проходе по внутреннему циклу можно добавить определение очередного минимального элемента и помещение его в начало массива. То есть, можно объединить алгоритм сортировки пузырьком и алгоритм [[Сортировка выбором|сортировки выбором]]. При этом количество проходов по внутреннему циклу уменьшится вдвое, но более чем вдвое увеличится количество сравнений и после каждого прохода по внутреннему циклу добавится одна перестановка.

Псевдокод [[Устойчивая сортировка|устойчивой]] реализации объединённого алгоритма сортировки пузырьком и сортировки выбором:

== Пример работы алгоритма ==
Используя алгоритм сортировки пузырьком, отсортируем по возрастанию массив чисел, равный «5 1 4 2 8». Выделены те элементы, которые сравниваются на текущем этапе.
[[Файл:Bubble-sort-example-300px.gif|alt=Анимация, показывающая пример работы алгоритма.|thumb|Наглядная демонстрация алгоритма.]]
Первый проход:
: ('''5 1''' 4 2 8) ('''1 5''' 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.
: (1 '''5 4''' 2 8) (1 '''4 5''' 2 8), Меняет местами, так как <math>5>4</math>
: (1 4 '''5 2''' 8) (1 4 '''2 5''' 8), Меняет местами, так как <math>5>2</math>
: (1 4 2 '''5 8''') (1 4 2 '''5 8'''), Теперь, ввиду того, что элементы стоят на своих местах (<math>8>5</math>), алгоритм не меняет их местами.

Второй проход:
: ('''1 4''' 2 5 8) ('''1 4''' 2 5 8)
: (1 '''4 2''' 5 8) (1 '''2 4''' 5 8), Меняет местами, так как <math>4>2</math>
: (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)

Теперь массив отсортирован и алгоритм может быть завершён.

== Пример реализации ==
Пример реализации алгоритма сортировки пузырьком на языке Java:
<source lang="java">
    public void sort(int[] data) {
        int n = data.length;
        for (int j = 1; j < n; j++) {
            boolean isSorted = true;
            for (int i = 0; i < n - j; i++) {
                if (data[i] > data[i + 1]) {
                    int tmp = data[i];
                    data[i] = data[i + 1];
                    data[i + 1] = tmp;
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
        }
    }
</source>

== Ссылки ==
{{Навигация
|Викиучебник = Примеры реализации сортировки пузырьком
}}
* [https://airtucha.github.io/SortVis/ Динамическая визуализация 7 алгоритмов сортировки с открытым исходным кодом]
* {{source|Q21694522|part=Глава 3. Метод грубой силы: Пузырьковая сортировка|pages=144—146}}

{{Нет источников |дата=2024-10-20}}
{{ВС}}
{{Алгоритмы сортировки}}

[[Категория:Алгоритмы сортировки]]