Как сделать сортировку пузырьком
Добавил пользователь Алексей Ф. Обновлено: 05.10.2024
Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
Описание алгоритма:
Идея данной сортировки заключается в попарном сравнении соседних элементов, начиная с нулевого в массиве. Больший элемент при этом в конце первой итерации оказывается на месте последнего элемента массива, и в следующих итерациях мы его уже не сравниваем его с остальными элементами (то есть у нас будет n-1 сравнений). Затем таким же образом мы находим второй по максимальности элемент и ставим его на предпоследнее место, и т. д. После всех итераций получится, что на месте нулевого элемента окажется элемент с наименьшим числовым значением, а на месте последнего – с наибольшим числовым значением. Таким образом у нас как бы “всплывают” элементы от большего к меньшему.
Примечание: можно также реализовать последовательность от меньшего к большему. В коде это лишь замена знака “>” на знак “ 2 9 4 1 0
Так как 7 больше, чем 2, мы меняем эти элементы местами. Получается массив:
2 7 9 4 1 0
Далее мы сравниваем 7 и 9.
2 7<>9 4 1 0
Число 9 больше, чем 7. Значит 7 остаётся на своём месте. Теперь мы будем сравнивать число 9 с остальными числами и, если 9 будет больше, чем соседние с ним числа, то будет меняться местами с ними.
2 7 9<>4 1 0
2 7 4 9<>1 0
2 7 4 1 9<>0
2 7 4 1 0 9
Большего числа, чем 9 в нашем массиве не оказалось, поэтому 9 занимает последний элемент в массиве. На этом первая итерация окончена. Теперь мы найдём следующее число, которое по значению будет меньше 9, но больше остальных чисел. Причём нам незачем больше трогать 9, так как оно уже на своём месте и в любом случае у него самое больше числовое значение. Поэтому количество шагов в итерации у нас уменьшается на 1 (n-1).
Вторая итерация. Мы опять “захватываем” нулевой элемент массива (2) и сравниваем его с соседним.
2<>7 4 1 0 9
Число 2 меньше, чем 7, поэтому они не будут меняться местами, а на следующем шаге будет сравниваться число 7 со следующим соседним элементом.
2 7<>4 1 0 9
2 4 7<>1 0 9
2 4 1 7<>0 9
Отлично, мы нашли второй элемент, и он занимает предпоследнее место в массиве. Вторая итерация окончена. Опять уменьшаем шаги итерации на 1, так как нам не надо больше сравнивать оставшиеся числа с 7.
После второй итерации наш массив выглядит так:
2 4 1 0 7 9
Третья итерация. Повторяем всё точно так же. Начинаем с нулевого элемента и ищем большее значение среди оставшихся чисел.
2<>4 1 0 7 9
2 4<>1 0 7 9
2 1 4<>0 7 9
2 1 0 4 7 9
Третья итерация окончена. Начинаем четвертую и не забываем уменьшить шаги итерации на 1.
2<>1 0 4 7 9
1 2<>0 4 7 9
1 0 2 4 7 9
Осталась последняя итерация и сравнение лишь двух чисел:
1<>0 2 4 7 9
Сортировка окончена. Наш упорядоченный массив теперь выглядит вот так:
0 1 2 4 7 9
Код программы:
Программу будем делать в консоли. Для начала создадим функцию самой сортировки (перед функцией main):
Алгоритм сортировки массива “пузырьковая сортировка” рассматривается практически во всех учебниках по программированию на С++. Его легко понять начинающим. Он наглядный и очень простой.
На практике этот алгоритм почти никто не использует, так как он медлительный и есть более быстрые и усовершенствованные алгоритмы. Мы также разберем его потому, что сортировка “пузырьком” – это основа некоторых более эффективных алгоритмов, которые будут изложены в следующих статьях. Это “быстрая” сортировка, “пирамидальная” сортировка и “шейкерная” сортировка.
Как работает “пузырьковая” сортировка? Допустим у нас есть неотсортированный массив чисел из 5-ти элементов и нам предстоит разместить значения по возрастанию. Для наглядности, на рисунке изобразим этот массив вертикально “Исходный массив”.
Алгоритм сортировки “пузырьком” состоит в повторении проходов по массиву с помощью вложенных циклов. При каждом проходе по массиву сравниваются между собой пары “соседних” элементов. Если числа какой-то из сравниваемых пар расположены в неправильном порядке – происходит обмен (перезапись) значений ячеек массива.
Образно говоря в нашем примере 2 “легче” чем 3 – поэтому обмен есть, далее 2 “легче” чем 7 – снова обмен и т.д. При сравнении нулевого и первого элемента на нашем рисунке обмена нет, так как 2 “тяжелее” чем 1. Таким образом более “легкое” значение, как пузырек в воде, поднимается вверх до нужной позиции. Вот почему у этого алгоритма такое название.
Рассмотрим алгоритм сортировки “пузырьком” в работе:
Внимательно разобрав данный пример с подробными комментариями, вам должно быть все понятно. Результат на экране такой:
Дополнить можно следующим: после того, как внутренний цикл отработает один раз, минимальное значение массива будет занимать нулевую ячейку. Поэтому при повторном проходе, очередное минимальное значение из оставшихся надо будет разместить в следующей ячейке (i + 1).
Таким образом нет необходимости сравнивать между собой все элементы массива снова и количество обрабатываемых значений уменьшается на 1. При сортировке “пузырьком” необходимо пройти SIZE – 1 итераций внешнего цикла, так как сравнивать один элемент с самим собой – смысла нет.
Не будем забывать то, о чем мы говорили в самом начале – алгоритм “пузырьковой” сортировки малоэффективен и медлителен. Если у нас есть частично отсортированный массив и необходимо переместить в начало только одно значение, он все равно будет проходить все итерации циклов. То есть производить сравнение уже отсортированных значений массива, хотя этого уже можно и не делать.
Давайте немного улучшим эту ситуацию. Добавим в код еще одну переменную-“флажок”, которая будет давать знать, произошел ли обмен значений на данной внешнего цикла итерации или нет. Перед тем, как войти во внутренний цикл, “флажок” будет сбрасываться в 0.
Если обмен значениями в этом цикле случится – “флажку” будет присвоено значение 1, если нет – то он останется равным 0. В последнем случае (если “флажок” равен 0) – обменов не было и массив полностью отсортирован. Поэтому программе можно досрочно выйти из циклов, чтобы не тратить время попусту на последующие ненужные сравнения.
При работе с массивами данных не редко возникает задача их сортировки по возрастанию или убыванию, т.е. упорядочивания. Это значит, что элементы того же массива нужно расположить строго по порядку. Например, в случае сортировки по возрастанию предшествующий элемент должен быть меньше последующего (или равен ему).
Решение
Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировкаметодом пузырька, который также называют методом простого обмена. В чем же он заключается, и почему у него такое странное название: "метод пузырька"?
Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).
Алгоритм сортировки прямым обменом основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы. Как и в методе прямого выбора, совершаются проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к началу массива.
Результат выполнения
Анализ алгоритма
Число сравнений в алгоритме прямого обмена
С = (n 2 - n)/2,
а минимальное, среднее и максимальное число перемещений элементов равно соответственно
Mmin = 0,
Mср = 3(n2 - n)/2,
Mmax = 3(n2 - n)/4.
Читайте также: