Bubble Sort algorithm
The solution below implements the Bubble Sort algorithm, which is a simple comparison-based sorting algorithm.
# O(n) time | O(1) space
def bubble_sort(array):
for i in range(0, len(array)):
for j in range(i+1, len(array)):
if array[i] > array[j]:
array[i],array[j]=array[j], array[i]
return array
print("bubble_sort::", bubble_sort([8, 5, 2, 9, 5, 6, 3]))
Solution Walkthrough
Initialization
The function bubble_sort takes an array as input.
Outer Loop (i)
The outer loop iterates over each element of the array from index 0 to len(array) - 1 representing each pass of the algorithm.
Inner Loop (j)
The inner loop iterates over the elements of the array from index i+1 to len(array) - 1 comparing each element with the next one.
Comparison
Within the inner loop, for each pair of adjacent elements (array[i], array[j]), if array[i] is greater than array[j], it swaps the elements.
The swapping operation is done using Python's tuple assignment feature: array[i], array[j] = array[j], array[i].
This process of comparing and swapping continues until the inner loop completes its iterations.
Result
After the outer loop completes all its iterations, the sorted array is returned.
Time Complexity
In this section, I cover the worst-case, average-case, and best-case time complexity.
Worst-Case Time Complexity
The worst-case time complexity of Bubble Sort is O(n^2), where n is the number of elements in the array. This is because in the worst case, the algorithm makes comparisons and swaps in each pass, resulting in a quadratic number of operations.
Best-Case Time Complexity
The best-case time complexity is O(n), which occurs when the array is already sorted. However, even in the best case, Bubble Sort still requires iterating over the entire array to confirm that it is sorted.
Average-Case Time Complexity
The average-case time complexity is also O(n^2), making Bubble Sort inefficient for large datasets.
Space Complexity
The space complexity of Bubble Sort is O(1), as it only requires a constant amount of additional space for temporary variables used in the swapping operation.
Example:
For example, given the input array [8, 5, 2, 9, 5, 6, 3], the Bubble Sort algorithm would rearrange the elements in ascending order as follows:
Pass 1: [5, 2, 8, 5, 6, 3, 9]
Pass 2: [2, 5, 5, 6, 3, 8, 9]
Pass 3: [2, 5, 5, 3, 6, 8, 9]
Pass 4: [2, 5, 3, 5, 6, 8, 9]
Pass 5: [2, 3, 5, 5, 6, 8, 9]
Pass 6: [2, 3, 5, 5, 6, 8, 9]
Pass 7: [2, 3, 5, 5, 6, 8, 9]
Updated Implementation
The updated Bubble Sort algorithm adds an optimization by introducing a flag (is_sorted) to check whether any swaps were made during a pass.
If no swaps were made in a pass, it means the array is already sorted, and the algorithm terminates early.
def bubble_sort_updated(array):
is_sorted =False
counter =0
while not is_sorted:
is_sorted=True
for i in range(len(array)-1-counter):
if array[i] > array[i+1]:
swap(i, i+1, array)
is_sorted=False
counter +=1
return array
def swap(i, j, array):
array[i], array[j] =array[j],array[i]
print("bubble_sort updated::", bubble_sort_updated([8, 5, 2, 9, 5, 6, 3]))
The updated Bubble Sort offers a minor improvement in performance over the original Bubble Sort by terminating early when the array is already sorted.
However, both algorithms have the same worst-case time complexity and space complexity.
The choice between them depends on the specific requirements of the problem and the characteristics of the input data.