Bubble Sort in Python
For most people, Bubble Sort is likely the first sorting algorithm they heard of in their Computer Science course.
It’s highly intuitive and easy to «translate» into code, which is important for new software developers so they can ease themselves into turning ideas into a form that can be executed on a computer. However, Bubble Sort is one of the worst-performing sorting algorithms in every case except checking whether the array is already sorted, where it often outperforms more efficient sorting algorithms like Quick Sort.
Bubble Sort
The idea behind Bubble Sort is very simple, we look at pairs of adjacent elements in an array, one pair at a time, and swap their positions if the first element is larger than the second, or simply move on if it isn’t. Let’s look at an example and sort the array 8, 5, 3, 1, 4, 7, 9:
If you focus on the first number, the number 8 , you can see it «bubbling up» the array into the correct place. Then, this process is repeated for the number 5 and so on.
Implementation
With the visualization out of the way, let’s go ahead and implement the algorithm. Again, it’s extremely simple:
def bubble_sort(our_list): # We go through the list as many times as there are elements for i in range(len(our_list)): # We want the last pair of adjacent elements to be (n-2, n-1) for j in range(len(our_list) - 1): if our_list[j] > our_list[j+1]: # Swap our_list[j], our_list[j+1] = our_list[j+1], our_list[j] Now, let’s populate a list and call the algorithm on it:
our_list = [19, 13, 6, 2, 18, 8] bubble_sort(our_list) print(our_list) Optimization
The simple implementation did its job, but there are two optimizations we can make here.
When no swaps are made, that means that the list is sorted. Though, with the previously implemented algorithm, it’ll keep evaluating the rest of the list even though it really doesn’t need to. To fix this, we’ll keep a boolean flag and check if any swaps were made in the previous iteration.
If no swaps are made, the algorithm should stop:
def bubble_sort(our_list): # We want to stop passing through the list # as soon as we pass through without swapping any elements has_swapped = True while(has_swapped): has_swapped = False for i in range(len(our_list) - 1): if our_list[i] > our_list[i+1]: # Swap our_list[i], our_list[i+1] = our_list[i+1], our_list[i] has_swapped = True The other optimization we can make leverages the fact that Bubble Sort works in such a way that the largest elements in a particular iteration end up at the end of the array.
The first time we pass through the list the position n is guaranteed to be the largest element, the second time we pass through the position n-1 is guaranteed to be the second-largest element and so forth.
This means that with each consecutive iteration we can look at one less element than before. More precisely, in the k-th iteration, only need to look at the first n — k + 1 elements:
def bubble_sort(our_list): has_swapped = True num_of_iterations = 0 while(has_swapped): has_swapped = False for i in range(len(our_list) - num_of_iterations - 1): if our_list[i] > our_list[i+1]: # Swap our_list[i], our_list[i+1] = our_list[i+1], our_list[i] has_swapped = True num_of_iterations += 1 Time Comparison
Let’s go ahead and compare the time it takes for each of these code snippets to sort the same list a thousand times using the timeit module:
Free eBook: Git Essentials
Check out our hands-on, practical guide to learning Git, with best-practices, industry-accepted standards, and included cheat sheet. Stop Googling Git commands and actually learn it!
Unoptimized Bubble Sort took: 0.0106407 Bubble Sort with a boolean flag took: 0.0078251 Bubble Sort with a boolean flag and shortened list took: 0.0075207 There isn’t much of a difference between the latter two approaches due to the fact that the list is extremely short, but on larger lists — the second optimization can make a huge difference.
Conclusion
In the most inefficient approach, Bubble Sort goes through n-1 iterations, looking at n-1 pairs of adjacent elements. This gives it the time complexity of O(n 2 ), in both best-case and average-case situations. O(n 2 ) is considered pretty horrible for a sorting algorithm.
It does have an O(1) space complexity, but that isn’t enough to compensate for its shortcomings in other fields.
However, it’s still a big part of the software development community and history, and textbooks almost never fail to mention it when talking about basic sorting algorithms.
Русские Блоги
Публичный аккаунт WeChat: отличная трата
Если у вас есть какие-либо вопросы или предложения, оставьте сообщение в фоновом режиме, и я сделаю все возможное, чтобы решить вашу проблему.
Что такое пузырьковая сортировка?
Я считаю, что многие друзья, которые связались с алгоритмом, понимают пузырьковую сортировку, так что же такое пузырьковая сортировка? Bubble sorting, английское имя (Bubble Sort) — это базовый алгоритм сортировки обмена, который часто используется в повседневной работе, например, данные страницы должны быть отсортированы по времени, что по сути является своего рода сортировкой пузырьков.
Друзья, которые пили колу, знают, что пузырьки в коле будут всплывать вверх — это самый яркий пример пузырьковой сортировки. Что касается некоторых друзей, то сначала поднимаются большие пузыри или сначала маленькие? Это зависит от ваших потребностей контроля.
Сначала перейдите к движущемуся изображению, а затем объедините код, чтобы представить процесс выполнения алгоритма сортировки пузырьков.
Базовое издание
def bubble_sort(list): x = len(list) # Этот цикл отвечает за настройку количества пузырьковых сортировок for i in range(x - 1): # Этот цикл отвечает за контроль количества сравниваемых элементов for j in range(0, x - 1 - i): # Заказ на обмен if list[j] > list[j + 1]: list[j], list[j + 1] = list[j +1], list[j] return list list = [3,1,2,4,5] print(bubble_sort(list)) Из изображения gif в сочетании с кодом видно, что даже если упорядочены некоторые элементы в текущей последовательности (последние два элемента 4 и 5 последовательности сравнивать не следует), обход элементов все равно будет выполнен, но эта операция Бессмысленно. Это, очевидно, приводит к неэффективности и потреблению ресурсов. В этом случае временная сложность алгоритма сортировки пузырьков составляет O (N ^ 2)
Ввиду низкой эффективности базовой версии пузырьковой сортировки появилась улучшенная версия.
Улучшенная версия
В базовой версии известно, что даже если упорядочены некоторые элементы в текущей последовательности (например, последние 4, 5), обход элемента все равно будет выполнен. И наша улучшенная версия должна решить эту проблему.
def bubble_sort(list): x = len(list) # Этот цикл отвечает за настройку количества пузырьковых сортировок for i in range(x - 1): # Упорядоченная отметка, инициал каждого раунда - true, используется для определения необходимости обмена элементами isSorted = True # Этот цикл отвечает за контроль количества сравниваемых элементов for j in range(0, x - 1 - i): # Заказ на обмен if list[j] > list[j + 1]: list[j], list[j + 1] = list[j +1], list[j] # Установить поведение обмена на False isSorted = False # Нет обменного поведения (isSorted = True), пропустите этот цикл напрямую if isSorted: break return list list = [3,1,2,4,5] print(bubble_sort(list)) Бит флага isSorted добавляется в приведенный выше код с использованием логической переменной isSorted в качестве маркера. Если элементы заменяются в этом раунде сортировки, это означает, что последовательность не в порядке, если нет обмена элементами, это означает, что последовательность уже в порядке и непосредственно выпрыгивает из большого цикла.
Наконец, если вы заинтересованы в Python и Java, нажмите и удерживайте QR-код, чтобы перейти к моей общедоступной учетной записи. Я постараюсь принести вам пользу. Мне не нужно это ценить, у меня нет возможности, я достоин этого. Просто игнорируйте это, если вы не помогаете.
Алгоритм пузырьковой сортировки — реализация на Python
Алгоритм пузырьковой сортировки является довольно простым. Он выполняет итерации по списку и сравнивает элементы попарно, заодно меняя их местами. Это происходит до тех пор, пока крупные элементы не «всплывут» (аналогия с пузырьками воздуха) в начало списка. Более мелкие, соответственно, останутся на «дне».
Итак, поначалу происходит сравнение первых двух элементов списка. В случае, если первый элемент больше, элементы меняются местами. Если же элементы находятся в нужном порядке, всё остаётся без изменений. Второй этап — переход к следующей паре, значения которой сравниваются и меняются местами в случае необходимости. Так происходит, пока пары элементов в списке не закончатся.
Когда конец списка достигнут, процесс повторяется для каждого элемента. Но это неэффективно, если нам надо сделать в массиве, к примеру, лишь один обмен. Дело в том, что алгоритм будет повторяться n 2 раз, даже когда список уже отсортирован.
Следовательно, алгоритм надо оптимизировать, для чего необходимо понимать, когда его останавливать, то есть знать, когда список отсортирован. Для остановки алгоритма следует ввести переменную-флаг. Если значения меняются местами, мы устанавливаем флаг в значение True, дабы повторить процесс сортировки. В случае, когда перестановок не произошло, флаг остаётся False, в результате чего алгоритм останавливается. Давайте посмотрим, как это реализовать на практике.
Реализация
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)Таким образом, алгоритм будет работать в цикле while и прерываться, если элементы ни разу не менялись местами. Сначала мы присвоим swapped значение True, чтобы наш алгоритм запустился хотя бы раз.
Что касается времени сортировки, то даже в самом худшем случае, если список изначально будет отсортирован по убыванию, затраты времени будут равны O(n 2 ), где n — число элементов списка.