bubble_sort.py

# A simple implementation of bubble sort

defbubbleSort(arr):
# travese the whole array
foriinrange(len(arr)):

# last i elements are already in place
forjinrange(0, len(arr)-i-1):

ifarr[j] >arr[j+1]:
arr[j], arr[j+1] =arr[j+1], arr[j]

returnarr

# Approach 2: This algorithm will run for O(n^2) even if the array is
# already sorted. For avoiding this, we can check if elements are swapped
# in each pass. We will break the loop in case they are not

# Time Complexity: O(n^2) - Average or Worst Case; O(n) - Best case [Array is already sorted]

defbubbleSortOptimized(arr):
foriinrange(len(arr)):
swapped=False

forjinrange(0, len(arr)-i-1):

ifarr[j] >arr[j+1]:
arr[j], arr[j+1] =arr[j+1], arr[j]
swapped=True

# if no elements are swapped, break the loop
ifswapped==False:
break

returnarr

if__name__="__main__":
arr= [2, 6, 1, 5, 3, 4]
res=bubbleSort(arr)
print(res)