Introduction to Bubble Sort
Bubble sort works by iterating through the array repeatedly, comparing adjacent elements and swapping them if they are in the wrong order.
The algorithm keeps track of the sorted partition of the array and continues sorting the remaining unsorted partition until the entire array is sorted.
This process is repeated until the array is fully sorted. It starts with the first pair of elements and continues until the last pair.
It is named as “bubble sort” because smaller elements “bubble” to the top of the list.
Example
Let’s say we have an array [5, 2, 8, 3, 1].
In the first iteration, the algorithm compares 5 and 2, swaps them to get [2, 5, 8, 3, 1].
Then it compares 5 and 8, no swap needed. It goes on like this until it reaches the end of the array. After the first iteration, the largest element (8) is in its correct position at the end of the array.
The remaining unsorted partition is [2, 3, 1]. The algorithm continues with the second iteration, again comparing and swapping elements until the array is sorted.
The final sorted array will be [1, 2, 3, 5, 8].
To see bubble sort in action take a look at this Scratch project.
Python Code for Bubble Sort
def bubble_sort(arr):
n = len(arr)
for i in range(n):
# Flag to optimize the algorithm; set to False if no swaps are made in a pass
swapped = False
# Last i elements are already in place, so we don't need to check them
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
# Swap the elements
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# If no two elements were swapped in the inner loop, the array is already sorted
if not swapped:
break
# Example usage:
my_list = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(my_list)
print("Sorted array is:", my_list)