#Author: OMKAR PATHAK

#This program shows an example of bubble sort using Python

# Bubblesort is an elementary sorting algorithm. The idea is to

# imagine bubbling the smallest elements of a (vertical) array to the

# top; then bubble the next smallest; then so on until the entire

# array is sorted. Bubble sort is worse than both insertion sort and

# selection sort. It moves elements as many times as insertion sort

# (bad) and it takes as long as selection sort (bad). On the positive

# side, bubble sort is easy to understand. Also there are highly

# improved variants of bubble sort.

# Best O(n^2); Average O(n^2); Worst O(n^2)

def bubbleSort(List):

for i in range(len(List)):

for j in range(len(List) - 1, i, -1):

if List[j] < List[j - 1]:

List[j], List[j - 1] = List[j - 1], List[j]

return List

if __name__ == '__main__':

List = [3, 4, 2, 6, 5, 7, 1, 9]

print('Sorted List:',bubbleSort(List))