Bubble Sort

• Idea: Find the right position of each element and place it there
• TC: $n^2$
• SC: 1 (In-place)

def bubbleSort(arr):
	n = len(arr)
	for i in range(0, n):
		swapped = False
		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 swapped == False:
			break
 
 
if __name__ == '__main__':
	arr = [9,2,4,1,5,4,7,3,6]
	print(f'Array: {arr}')
	bubbleSort(arr)
	print(f'Sorted Array: {arr}')