сортировка пузырьком питон код
Сортировка пузырьком
В процессе выполнения данного алгоритма элементы с большими значениями оказываются в конце списка, а элементы с меньшими значениями постепенно перемещаются по направлению к началу списка. Образно говоря, тяжелые элементы падают на дно, а легкие медленно всплывают подобно пузырькам воздуха.
В сортировке методом пузырька количество итераций внешнего цикла определяется длинной списка минус единица, так как когда второй элемент становится на свое место, то первый уже однозначно минимальный и находится на своем месте.
Количество итераций внутреннего цикла зависит от номера итерации внешнего цикла, так как конец списка уже отсортирован, и выполнять проход по этим элементам смысла нет.
Пусть имеется список [6, 12, 4, 3, 8].
За первую итерацию внешнего цикла число 12 переместится в конец. Для этого потребуется 4 сравнения во внутреннем цикле:
Результат: [6, 4, 3, 8, 12]
За вторую итерацию внешнего цикла число 8 переместиться на предпоследнее место. Для этого потребуется 3 сравнения:
Результат: [4, 3, 6, 8, 12]
На третьей итерации внешнего цикла исключаются два последних элемента. Количество итераций внутреннего цикла равно двум:
Результат: [3, 4, 6, 8, 12]
На четвертой итерации внешнего цикла осталось сравнить только первые два элемента, поэтому количество итераций внутреннего равно единице:
Результат: [3, 4, 6, 8, 12]
Реализация сортировки пузырьком с помощью циклов for
Пример выполнения кода:
С помощью циклов while
Функция сортировки пузырьком на Python
Сортировка методом пузырька в Python
На сегодняшний день создано множество алгоритмов сортировки, каждый из которых решает весьма распространенную задачу — сортировку данных.
Сортировка пузырьком — это один из самых простых, но и малоэффективных алгоритмов, который используется для сортировки небольших массивов.
Алгоритмы сортировки на собеседовании
Алгоритмов сортировки достаточно много, и вряд ли можно встретить программиста, который может по памяти написать реализацию хотя бы половины из них.
На самом деле, программисты просто гуглят необходимую реализацию. Конечно, они имеют представление о принципах их работы, потому что в своё время рассмотрели несколько алгоритмов, как, например, сортировка пузырьком.
На собеседованиях спрашивают про алгоритмы сортировки, но это не значит, что от будущего работника требуют написать их реализацию или придумать свой. Работодатель требует от специалиста следующее:
Метод пузырька
Сортировка пузырьком в основном применяется в учебных проектах. В реальной практике её заменяют более эффективные алгоритмы, однако сортировка пузырьком лежит в основе некоторых из них.
В общем случае алгоритм сортировки пузырьком следующий:
В алгоритме используется два цикла: основной и вложенный. В результате одного прохода вложенного цикла наибольший элемент помещается в конец массива, а наименьший смещается на одну позицию ближе к началу.
Внешний цикл в худшем случае совершает N (кол-во элементов) — 1 проходов, то есть внутренний цикл выполняется N-1 раз.
Таким образом, в каждом проходе совершается серия обменов элементов так, что наибольший элемент передвигается в конец массив перед элементом, который переместился туда в прошлой итерации. Процесс происходит до тех пор, пока массив не будет отсортирован.
Сложность алгоритма
Сложность алгоритма позволяет дать ему оценку по времени выполнения, то есть определяет его эффективность. Можно выражать сложность по-разному, но чаще всего используется асимптотическая сложность, которая определяет его эффективность при стремлении входных данных к бесконечности.
Точное время выполнения алгоритма не рассматривается, потому что оно зависит слишком от многих факторов: мощность процессора, тип данных массива, используемый язык программирования.
Следует понимать, что с помощью асимптотической функции нельзя точно вычислить время работы алгоритма. Например, дана последовательность «6 5 4 3 2 1», для её сортировки придется сделать максимальное количество проходов. Такой случай называют наихудшим. Если дана последовательность «3 1 2 4 5», то количество проходов будет минимально, соответственно сортировка пройдет гораздо быстрее. Если же дан уже отсортированный массив, то алгоритму сортировки и вовсе не нужно совершать проходов. Это называется наилучшим случаем.
Реализация на Python
Сортировку пузырьком лучше вывести в отдельную функцию. Код функции будет выглядеть так:
Реализовать обмен значений соседних элементов можно в одну строку, использовав множественное присваивание, тогда код будет выглядеть так:
Множественное присваивание — одна из полезных фич Python, позволяющее не вводить дополнительную переменную для обмена значений двух и более переменных.
Чтобы продемонстрировать работу функции пузырьковой сортировки, создадим список, которые необходимо отсортировать:
Отсортируем его с помощью нашей функции и выведем на экран:
Заключение
Метод пузырька гораздо менее эффективен других алгоритмов, однако он имеет простую и понятную реализацию, поэтому часто используется в учебных целях. Кроме того, пузырьковая сортировка может использоваться для работы с небольшими массивами данных.
Знания особенностей алгоритмов сортировки, их сложности и принципов реализации в общем виде пригодятся каждому программисту, желающему пройти собеседование и стать Python-разработчиком.
Сортировка пузырьком питон код
Довольно часто при решении задач приходится сортировать значения в списке (массиве) по возрастанию или убыванию. Существует большое количество различных алгоритмов сортировки. Они отличается друг от друга временем выполнения (вычислительной сложностью), используемой памятью, а также сложностью в понимании и реализации.
Можете просмотреть следующее видео — изображающее принцип работы некоторых алгоритмов сортировки:
Один из самый простых алгоритмов сортировки, изучаемый в школьном курсе информатики — «Сортировка методом Пузырька». Его нельзя назвать быстрым, но он очень прост в понимании и реализации. Подходит для сортировки небольших списков (массивов).
Работу данного алгоритма представил в виде танца коллектив из Финляндии
Как видно из видео процесс сортировки заключается в следующем:
Например:
Дан список (массив): 0, 5, 8, 4, 9, 3
Расположим элементы списка в процессе убывания. Т.е. если элемент меньше своего соседа справа — меняется с ним местами.
После первого прохождения по списку первый нолик становится на последнее место
Как можно заметить количество сравнений уменьшилось на единицу, так как число 0 — минимальное заняло свое законное место при первой итерации и сравнивать с ним нет смысла.
В итоге получаем отсортированный список:
Для списка из шести элементов достаточно выполнить пять «проходов» по списку, поочередно сравнивая соседние элементы.
Напишем программу сортировки методом Пузырька на Python 3.
Задачи:
Пузырьковая сортировка на Python и С#
В этом материале мы поговорим про алгоритм сортировки пузырьком (Bubble sort). Для примера попробуем отсортировать массив вручную, после чего напишем код для сортировки пузырьком на языке программирования Python и Си шарп.
Описание алгоритма
В процессе сортировки пузырьком происходит попарное сравнение соседних элементов массива, начиная с нулевого. После первой итерации самое большое число окажется на месте последнего, причем в дальнейших итерациях это значение уже задействоваться не будет (по сути, мы получим n-1 сравнений). Далее алгоритм находит второй по величине элемент, который ставится на предпоследнее место, потом третий и пр. В результате на месте нулевого элемента (не забываем, что нумерация в массиве начинается с нуля) окажется наименьшее число, а на месте последнего элемента – наибольшее. То есть мы можем сказать, что элементы от большего к меньшему «всплывают» по аналогии с пузырьками.
Проговорим алгоритм еще раз:
Важно понимать, что при реализации сортировки применяют 2 цикла: основной и вложенный (внутренний цикл). По результатам одного прохода внутреннего цикла самый большой элемент смещается в конец массива, тогда как самый маленький перемещается к началу (на одну позицию).
Рассмотрим пример
Представьте, что у нас есть следующий массив:
В процессе первой итерации мы возьмем нулевой элемент (это 7) и сравним его с соседним. Так как семь больше двух, числа меняются своими местами. То есть массив меняется:
2 7 9 4 1 0
Потом происходит сравнение второго и третьего числа. Так как изначально 9 больше семи, то семь остается на месте. Далее 9 последовательно сравнивается с остальными значениями и таким образом постепенно перемещается в самый конец массива (так как числа, большего, чем 9, в массиве нет, девятка занимает заслуженное последнее место).
2 7 4 1 0 9
Первая итерация закончена, количество шагов уменьшилось на 1 (n-1), то есть 9 находится там, где надо. Больше это число не затрагивается.
Во второй итерации все опять начинается с нулевого элемента массива (в нашем случае это двойка) с последующими сравнениями и перемещениями. В результате массив будет выглядеть следующим образом:
2 4 1 0 7 9
И так далее. Итоговый вид массива после сортировки по методу пузырьком вы можете видеть ниже:
Как видите, ничего сложного в этом нет.
Реализация на Си шарп
Чтобы реализовать сортировку пузырьком, сначала над создать саму функцию сортировки, которая будет располагаться в итоге перед функцией main:
Пузырьковая сортировка в Python
Сортировка пузырьком – это простой алгоритм среди различных алгоритмов сортировки. Изучим его как первый алгоритм сортировки. Его легко освоить и он интуитивно очень понятен. Его несложно реализовать в коде, что очень выгодно для начинающих разработчиков программного обеспечения. Минус алгоритма в том, что для сортировки элементов данный метод производит проверку каждый раз, независимо от того, сортируется массив или нет.
Концепция пузырьковой сортировки
Разберемся на примере.
Мы создаем список элементов, в котором хранятся целые числа
list1 = [5, 3, 8, 6, 7, 2]
Так алгоритм сортирует элементы:
Первая итерация
Он сравнивает первые два элемента, и здесь 5> 3, а затем меняет их местами. Теперь у нас есть новый список –
Во втором сравнении 5 6, элементы меняются местами –
В четвертом сравнении 8> 7, элементы меняются местами –
В пятом сравнении 8> 2, также нужно их поменять местами –
На этом первая итерация завершена, и в конце мы получаем самый большой элемент. Теперь нам нужно len (list1) – 1
Вторая итерация
Пятая итерация
Мы видим, что наш список отсортирован с использованием метода пузырьковой сортировки.
Реализация в коде Python
Мы уже описывали технику пузырьковой сортировки. Теперь реализуем логику в коде Python.
В приведенном выше коде мы определили функцию bubble_sort(), которая принимает list1 в качестве аргумента.
Без использования временной переменной
Мы также можем поменять местами элементы, не используя временную переменную. У Python очень уникальный синтаксис. Мы можем использовать следующие строки кода.
Оптимизация реализации кода Python
Мы можем оптимизировать приведенный выше код, используя два метода. Свопы не производятся; это означает, что список отсортирован. В предыдущем методе оценивается полный список, хотя в этом нет необходимости.
Мы можем предотвратить ненужную оценку, используя логический флаг и проверяя, были ли сделаны какие-либо свопы в предыдущем разделе.
Во втором методе мы учитываем тот факт, что итерация заканчивается, когда самый большой элемент списка оказывается в конце списка.
В первый раз мы передаем самый большой элемент в конечную позицию, используя позицию n. Во второй раз мы проходим через позицию n-1, второй по величине элемент.
На каждой последующей итерации мы можем сравнивать на один элемент меньше, чем раньше. Точнее, на k-й итерации нужно сравнить только первые n – k + 1 элементов:
Сравнение времени
Давайте посмотрим на сравнение времени между приведенными выше фрагментами кода.
Все методы применимы для небольшого числа элементов, но если список состоит из многих элементов, то второй метод оптимизации имеет огромное значение.