In this post we'll see how to write Bubble sort program in Python. Bubble sort works by comparing and swapping adjacent elements.
Bubble sort algorithm
Bubble sort works as follows for sorting an array in ascending order-
You start from the left end and compare the first two elements (i.e. element at index 0 and index 1). If element on the left is greater than the element on right (element at 0 > element at 1) you swap those two.
Move to next index and compare the next two adjacent elements (i.e. element at index 1 and index 2). Again, if element on the left is greater than the element on right you swap them.
This process is repeated until you reach the rightmost element.
This is the first pass of the bubble sort and by the end of the first pass you have the greatest element at the rightmost end. In this sorting technique greatest elements bubble up to the higher indices of the array thus the name bubble sort.
This process is repeated n-1 times for an array of length n. Since there are a large number of comparisons and swaps Bubble sort is considered one of the slowest sorting algorithm.
For example, if you have an array [6, 3, 10, 7, 1] then the first pass can be depicted as follows.
In the first iteration, first two elements (6 and 3) are compared, since 6 is greater than 3 so elements are swapped. Same way in the next iteration 6 and 10 are compared and so on. By the end of the first pass greatest element in the array (10) bubbles up to the top of the array.
Because the last element is already at its intended position after the first pass, in the next pass only (N - 1) elements are considered thus the part of the array used is [3, 6, 7, 1].
Bubble Sort Python program
def bubble_sort(arr):
arr_length = len(arr)
for i in range(arr_length-1):
# reduce length by 1 in each pass
for j in range(arr_length-i-1):
if(arr[j] > arr[j+1]):
# swap using tuple assignment
arr[j+1], arr[j] = arr[j], arr[j+1]
arr = [17, 85, 0, 34, 7, -10, 82, 107, 2, 35]
bubble_sort(arr)
print('Sorted array ', arr)
Output
Sorted array [-10, 0, 2, 7, 17, 34, 35, 82, 85, 107]
Bubble sort time and space and complexity
Time complexity of bubble sort is O(n2) for worst and average case. Best case time complexity is O(n) which happens when the array is already sorted and you keep track of it.
def bubble_sort(arr):
arr_length = len(arr)
for i in range(arr_length-1):
#tracks if swapping happens or not
swapped = False
# reduce length by 1 in each pass
for j in range(arr_length-i-1):
if(arr[j] > arr[j+1]):
# swap using tuple assignment
arr[j+1], arr[j] = arr[j], arr[j+1]
swapped = True
if not swapped:
break
arr = [-10, 0, 2, 7, 17, 34, 35, 82, 85, 107]
bubble_sort(arr)
print('Sorted array ', arr)
No extra space is required so the space complexity of bubble sort is O(1).
That's all for the topic Bubble Sort Python Program. If something is missing or you have something to share about the topic please write a comment.
You may also like
No comments:
Post a Comment