Bubblesort Complexity Calculation

Question

I would like to know how I can demonstrate by induction calculation the complexity of the bubblesort algorithm, both in the best case and in the worst case.

def bubble_Sort(alist):

    for numc in range(len(alist)-1,0,-1):

        for i in range(numc):

            if alist[i]>alist[i+1]:

                temp = alist[i]

                alist[i] = alist[i+1]

                alist[i+1] = temp



alist = [54,26,93,17,77,31,44,55,20]

bubble_Sort(alist)

print(alist)

Answer 1

It depends on what you mean by "complexity", I will try to demonstrate through notation Big O. Bubble Sort consists of going through a list and changing the positions of the elements in order to get the list sorted, that is, it will be necessary to go through the entire list at least once.

Best case:
If the list is already sorted then no swap (swap) will be made, then we would have the best case, where we would have to compare the values in position 0, position 1, 2, ..., n-2, up to n-1, as all the values in their positions are lower than their successor neighbor, there would be no exchange, and we would just loop over the list, then on a list of n we would have a total of n-1, comparisons, for the Big O notation, we disregard the term -1, so we have, for the best case: O(n).

Worst case:
Bubblesort has its worst case when the list is in reverse order, in which case in the initial loop the item that was at position 0 will end at position n-1, let’s take an example:

lista = [5, 4, 3, 2, 1]
         ^
         Posição 0  

# Loop inicial
4, 5, 3, 2, 1
4, 3, 5, 2, 1
3, 4, 5, 2, 1
3, 4, 2, 5, 1
3, 4, 2, 1, 5 
            ^
            Posição n-1

The next loop will move the second highest value from the list to the n-2 position of the list.

lista_atualizada = [3, 4, 2, 1, 5]

 # Segundo loop
 3, 2, 4, 1, 5
 3, 2, 1, 4, 5 
          ^ Posição n-2

After n-1 loops the list will be sorted and the algorithm will still make one more loop before the return, the number of comparisons will be n(n-1) or n²-n , for the Big O notation, we remove the constant coefficients and the nondominant terms, and we will have: O(n²)