weiyunfei16
a3ac146cb4
Implement standard and optimized bubble sort algorithms with example usage. Co-Authored-By: Claude Opus 4.6 <noreply@anthropic.com>
58 lines
1.6 KiB
Python
58 lines
1.6 KiB
Python
def bubble_sort(arr):
|
|
"""
|
|
Sort an array using bubble sort algorithm.
|
|
|
|
Args:
|
|
arr (list): List of comparable elements to be sorted.
|
|
|
|
Returns:
|
|
list: Sorted list in ascending order.
|
|
"""
|
|
n = len(arr)
|
|
# Traverse through all array elements
|
|
for i in range(n):
|
|
# Last i elements are already in place
|
|
for j in range(0, n - i - 1):
|
|
# Traverse the array from 0 to n-i-1
|
|
# Swap if the element found is greater than the next element
|
|
if arr[j] > arr[j + 1]:
|
|
arr[j], arr[j + 1] = arr[j + 1], arr[j]
|
|
return arr
|
|
|
|
|
|
def bubble_sort_optimized(arr):
|
|
"""
|
|
Optimized bubble sort that stops if no swaps occur in a pass.
|
|
|
|
Args:
|
|
arr (list): List of comparable elements to be sorted.
|
|
|
|
Returns:
|
|
list: Sorted list in ascending order.
|
|
"""
|
|
n = len(arr)
|
|
for i in range(n):
|
|
swapped = False
|
|
# Last i elements are already in place
|
|
for j in range(0, n - i - 1):
|
|
if arr[j] > arr[j + 1]:
|
|
arr[j], arr[j + 1] = arr[j + 1], arr[j]
|
|
swapped = True
|
|
# If no two elements were swapped in inner loop, then break
|
|
if not swapped:
|
|
break
|
|
return arr
|
|
|
|
|
|
if __name__ == "__main__":
|
|
# Example usage
|
|
example_arr = [64, 34, 25, 12, 22, 11, 90]
|
|
print("Original array:", example_arr)
|
|
|
|
# Test standard bubble sort
|
|
sorted_arr = bubble_sort(example_arr.copy())
|
|
print("Sorted array (standard):", sorted_arr)
|
|
|
|
# Test optimized bubble sort
|
|
optimized_arr = bubble_sort_optimized(example_arr.copy())
|
|
print("Sorted array (optimized):", optimized_arr) |