Bubble sort is a simple sorting algorithm in which adjacent elements are compared to each other and swapped if the elements are not in intended order. It is a comparison based algorithm. This algorithm is not suitable for large data because of its not so good worst and average case time complexity O(n2), n is the number of elements.
Illustration:
for all elements in list
for adjacent elements of unsorted portion of list
if leftElement > rightElement
swap the elements
Time Complexity:
- Worst Case: O(n2)
- Average Case: O(n2)
- Best Case: O(n) Space Complexity: O(1)
Program for Bubble Sort:
def bubbleSort(data):
for i in range(len(data)):
for j in range(0, len(data) - i - 1):
if data[j] > data[j + 1]: #Reversing the comparison operator will result in descending order sort
(data[j], data[j + 1]) = (data[j + 1], data[j]) #Swap
inp=input("Enter the data: ").split()
data=[]
for i in inp:
data.append(int(i))
bubbleSort(data)
print('Sorted List: ')
print(data)