1 added
1 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Алгоритм пузырьковой сортировки является довольно простым. Он выполняет итерации по списку и сравнивает элементы попарно, заодно меняя их местами. Это происходит до тех пор, пока крупные элементы не "всплывут" (аналогия с пузырьками воздуха) в начало списка. Более мелкие, соответственно, останутся на "дне".</p>
1
<p>Алгоритм пузырьковой сортировки является довольно простым. Он выполняет итерации по списку и сравнивает элементы попарно, заодно меняя их местами. Это происходит до тех пор, пока крупные элементы не "всплывут" (аналогия с пузырьками воздуха) в начало списка. Более мелкие, соответственно, останутся на "дне".</p>
2
-
<p>Итак, поначалу происходит сравнение первых двух элементов списка. В случае, если первый элемент больше, элементы меняются местами. Если же элементы находятся в нужном порядк��, всё остаётся без изменений. Второй этап - переход к следующей паре, значения которой сравниваются и меняются местами в случае необходимости. Так происходит, пока пары элементов в списке не закончатся.</p>
2
+
<p>Итак, поначалу происходит сравнение первых двух элементов списка. В случае, если первый элемент больше, элементы меняются местами. Если же элементы находятся в нужном порядке, всё остаётся без изменений. Второй этап - переход к следующей паре, значения которой сравниваются и меняются местами в случае необходимости. Так происходит, пока пары элементов в списке не закончатся.</p>
3
<p>Когда конец списка достигнут, процесс повторяется для каждого элемента.<strong>Но это неэффективно</strong>, если нам надо сделать в массиве, к примеру, лишь один обмен. Дело в том, что алгоритм будет повторяться n2 раз, даже когда список уже отсортирован.</p>
3
<p>Когда конец списка достигнут, процесс повторяется для каждого элемента.<strong>Но это неэффективно</strong>, если нам надо сделать в массиве, к примеру, лишь один обмен. Дело в том, что алгоритм будет повторяться n2 раз, даже когда список уже отсортирован.</p>
4
<p>Следовательно, алгоритм надо оптимизировать, для чего необходимо понимать, когда его останавливать, то есть знать, когда список отсортирован. Для остановки алгоритма<strong>следует ввести переменную-флаг</strong>. Если значения меняются местами, мы устанавливаем флаг в значение True, дабы повторить процесс сортировки. В случае, когда перестановок не произошло, флаг остаётся False, в результате чего алгоритм останавливается. Давайте посмотрим, как это реализовать на практике.</p>
4
<p>Следовательно, алгоритм надо оптимизировать, для чего необходимо понимать, когда его останавливать, то есть знать, когда список отсортирован. Для остановки алгоритма<strong>следует ввести переменную-флаг</strong>. Если значения меняются местами, мы устанавливаем флаг в значение True, дабы повторить процесс сортировки. В случае, когда перестановок не произошло, флаг остаётся False, в результате чего алгоритм останавливается. Давайте посмотрим, как это реализовать на практике.</p>
5
<h2>Реализация</h2>
5
<h2>Реализация</h2>
6
def bubble_sort(nums): # Установим swapped в True, чтобы цикл запустился хотя бы раз swapped = True while swapped: swapped = False for i in range(len(nums) - 1): if nums[i] > nums[i + 1]: # Меняем элементы nums[i], nums[i + 1] = nums[i + 1], nums[i] # Установим swapped в True для последующей итерации swapped = True # Проверим, что всё работает random_list_of_nums = [5, 2, 1, 8, 4] bubble_sort(random_list_of_nums) print(random_list_of_nums)<p>Таким образом, алгоритм будет работать в цикле while и прерываться, если элементы ни разу не менялись местами. Сначала мы присвоим swapped значение True, чтобы наш алгоритм запустился хотя бы раз.</p>
6
def bubble_sort(nums): # Установим swapped в True, чтобы цикл запустился хотя бы раз swapped = True while swapped: swapped = False for i in range(len(nums) - 1): if nums[i] > nums[i + 1]: # Меняем элементы nums[i], nums[i + 1] = nums[i + 1], nums[i] # Установим swapped в True для последующей итерации swapped = True # Проверим, что всё работает random_list_of_nums = [5, 2, 1, 8, 4] bubble_sort(random_list_of_nums) print(random_list_of_nums)<p>Таким образом, алгоритм будет работать в цикле while и прерываться, если элементы ни разу не менялись местами. Сначала мы присвоим swapped значение True, чтобы наш алгоритм запустился хотя бы раз.</p>
7
<p>Что касается<strong>времени сортировки</strong>, то даже в самом худшем случае, если список изначально будет отсортирован по убыванию, затраты времени будут равны O(n2), где n - число элементов списка.</p>
7
<p>Что касается<strong>времени сортировки</strong>, то даже в самом худшем случае, если список изначально будет отсортирован по убыванию, затраты времени будут равны O(n2), где n - число элементов списка.</p>
8
<p>Вот и всё!</p>
8
<p>Вот и всё!</p>
9
<p><em>Возможно, вам также будет интересно:</em>1.<a>"Оцениваем сложность алгоритмов: что такое О(log n)?"</a>2.<a>"Реализуем пирамидальную сортировку на Python"</a>.</p>
9
<p><em>Возможно, вам также будет интересно:</em>1.<a>"Оцениваем сложность алгоритмов: что такое О(log n)?"</a>2.<a>"Реализуем пирамидальную сортировку на Python"</a>.</p>
10
<p><a>Источник</a></p>
10
<p><a>Источник</a></p>
11
11