bubble sort Algorithm
Bubble sort algorithm is a simple sorting technique that works by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm gets its name from the way smaller elements "bubble" to the top of the list as larger elements "sink" to the bottom, akin to the behavior of gas bubbles in a liquid. This comparison-based sorting algorithm is easy to understand and implement, making it a popular choice for teaching and learning the basics of sorting algorithms, although it is not efficient for large datasets.
The bubble sort algorithm starts at the beginning of the list and compares the first two elements. If the first element is greater than the second, the algorithm swaps them. It then moves on to the next pair of adjacent elements and performs the same comparison and swap operation if necessary. This process continues until the end of the list is reached. At this point, the largest element will have "bubbled" to the correct position at the end of the list. The algorithm then repeats the entire process, excluding the last sorted element, and continues this way until all the elements are sorted. Despite its simplicity, bubble sort has a worst-case and average-case time complexity of O(n^2), making it inefficient for large datasets compared to other sorting algorithms like quicksort and merge sort.
def bubble_sort(collection):
"""Pure implementation of bubble sort algorithm in Python
:param collection: some mutable ordered collection with heterogeneous
comparable items inside
:return: the same collection ordered by ascending
Examples:
>>> bubble_sort([0, 5, 2, 3, 2])
[0, 2, 2, 3, 5]
>>> bubble_sort([])
[]
>>> bubble_sort([-2, -45, -5])
[-45, -5, -2]
>>> bubble_sort([-23, 0, 6, -4, 34])
[-23, -4, 0, 6, 34]
>>> bubble_sort([-23, 0, 6, -4, 34]) == sorted([-23, 0, 6, -4, 34])
True
"""
length = len(collection)
for i in range(length - 1):
swapped = False
for j in range(length - 1 - i):
if collection[j] > collection[j + 1]:
swapped = True
collection[j], collection[j + 1] = collection[j + 1], collection[j]
if not swapped:
break # Stop iteration if the collection is sorted.
return collection
if __name__ == "__main__":
import time
user_input = input("Enter numbers separated by a comma:").strip()
unsorted = [int(item) for item in user_input.split(",")]
start = time.process_time()
print(*bubble_sort(unsorted), sep=",")
print(f"Processing time: {time.process_time() - start}")
