"Пузырьковая сортировка" - это алгоритм на языке Python, который используется для упорядочивания группы чисел от наименьшего к наибольшему. Алгоритм пузырьковой сортировки представляет собой простой метод, который легко понять и выполнить. Это хороший выбор для новичков, изучающих алгоритмы сортировки.
В этом блоге будет представлено подробное руководство по реализации пузырьковой сортировки в Python на многочисленных примерах.
Что такое пузырьковая сортировка в Python?
Пузырьковая сортировка - это способ сортировки, при котором два элемента сравниваются друг с другом и меняются местами, пока не окажутся в правильном порядке. Если они уже находятся в правильной последовательности, то ничего не происходит. Алгоритм пузырьковой сортировки - это простой способ сортировки в Python.
Работа с пузырьковой сортировкой в Python
Прямой алгоритм сортировки "Bubble Sort" работает путем многократного сравнения соседних элементов и их замены, если они расположены в неправильной последовательности. Алгоритм начинается с начала массива и переходит к сравнению двух начальных элементов. Если первый элемент/элементы больше второго элемента/элементов, то эти два элемента меняются местами. Затем алгоритм переходит к следующим двум элементам и повторяет цикл. Так продолжается до тех пор, пока мы не достигнем конца массива.
Алгоритм / Псевдокод пузырьковой сортировки
| 1 2 3 4 | function(array) for i rightvalue swap leftvalue and rightvalue end function |
Как реализовать пузырьковую сортировку в Python?
Для реализации пузырьковой сортировки в Python на основе алгоритма пузырьковой сортировки используется следующий код пользовательской функции:
| 1 2 3 4 5 6 7 8 9 10 11 12 | def bubble_sort(arr): for i in range(len(arr)): for j in range(0, len(arr) - i - 1): if arr[j] > arr[j + 1]: temp = arr[j] arr[j] = arr[j + 1] arr[j + 1] = temp data = [-5, -2, 10, 21, -9] bubble_sort(data) print('Array Sorted in Ascending Order:\n') print(data) |
В приведенном выше коде:
- Функция "bubbleSort()" определяется, принимая на вход массив.
- Работа функции заключается в многократном сравнении смежных элементов/элементов и их переключении, если они расположены в неправильной последовательности.
- Внутри функции инициализируются вложенные циклы.
- Функция состоит из двух циклов, которые проходят через массив. Первый цикл начинается с первого элемента, а второй цикл начинается с начала и идет до элемента, предшествующего последнему.
- На каждой итерации второго цикла функция сравнивает текущий элемент со следующим элементом.
- Если текущий элемент/элемент больше следующего, то они меняются местами.
- Переменная "temp" используется для временного хранения значения текущего элемента. Это необходимо, поскольку функция должна поменять местами значения двух элементов, но не может сделать это напрямую, не заменив значение следующего элемента.
- Наконец, функция "bubble_sort()", принимая в качестве аргумента массив "data", сортирует массив.
Оптимизация алгоритма пузырьковой сортировки при уже отсортированном массиве
Алгоритм проверяет все элементы, даже если они уже упорядочены. Это делает его более медленным. Чтобы ускорить его работу, мы можем добавить новую переменную "swapped". Если элементы поменяны местами, то swapped становится "True". Если нет, то она принимает значение "False". После каждой проверки, если значение swapped равно false, это означает, что элементы уже отсортированы, и нам не нужно проверять их снова. Это делает алгоритм более быстрым и качественным. Приведем пример кода, демонстрирующий этот процесс:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | def bubble_sort(arr): n = len(arr) swapped = False for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True if not swapped: break arr = [54, 44, 15, 22, 32, 21, 90] bubble_sort(arr) print("Sorted array:", arr) |
В приведенном выше коде:
- Функция "bubble_sort()" определяется, принимая на вход массив.
- Переменная "n" хранит длину массива, а переменная "swapped" является флагом, который устанавливается в значение "False".
- Внешний цикл "for" выполняет итерацию/проход по массиву, начиная с первого элемента, а внутренний цикл "for" выполняет итерацию/проход по массиву, начиная с начала и до последнего элемента.
- На каждой итерации внутреннего цикла функция сравнивает текущий элемент со следующим элементом. Если текущий элемент больше следующего, то эти два элемента меняются местами.
- Флаг "поменяно" устанавливается в "True", если в текущей итерации внутреннего цикла были произведены какие-либо замены.
- Если флаг swapped равен "False", то массив упорядочен или отсортирован, и внешний цикл прерывается.
- После определения функции она вызывается на указанном массиве.
Заключение
В Python алгоритм пузырьковой сортировки используется для сортировки вещей путем сравнения двух вещей рядом друг с другом и их перестановки до тех пор, пока они не окажутся в правильном порядке. Если вещи уже расположены по порядку, то при использовании алгоритма пузырьковой сортировки в Python ничего не происходит. В данной статье на многочисленных примерах продемонстрирован алгоритм "пузырьковой сортировки".