Bubble Sort

• Consider an array A = [7,5,4,6,1]. We take the first element i.e 7 and compare it with the next element i.e. 5. If the current element is greater than the next element, we swap and repeat till the end of the array. Which then gives us A = [5,4,6,1,7].
• So after 1st pass, we get the highest number at the end of an array. After the second pass, the second highest number gets the place A[-2]. Similarly, we run it for K(number of elements) passes, we get the sorted array.

def BubbleSort(A,n):
    for k in range(n):
        for i in range(n-k-1): #I have done n-k-1 as we do not want to go through all elements as last elements
            if A[i]>A[i+1]:
                temp = A[i]
                A[i] = A[i+1]
                A[i+1] = temp

This has a complexity of O(n^2) which is not what we are expecting.

We can do one more thing to improve the complexity. We can just set Flag which will be zero by default. And if there is any swap occuring while a pass,we can set it to one. After every loop, we can check if flag ==0, because if it is = 0 then no swaps have taken place during that pass and hence the list is sorted. There is no need for further passes

def BubbleSort(A,n):
    for k in range(n):
        flag = 0
        for i in range(n-k-1): #I have done n-k-1 as we do not want to go through all elements as last elements
            if A[i]>A[i+1]:
                temp = A[i]
                A[i] = A[i+1]
                A[i+1] = temp
                flag = 1
        if flag == 0:
            break

Best Case: O(n)

Average Case: O(n^2)

Worst Case: O(n^2)