BubbleSort complexity calculation
I would like to know how I can demonstrate by calculation induction 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)
1 answers
Depends on what you mean by "complexity", I will try to demonstrate through the notation Big O. Bubble sort consists of going through a list and changing the positions of the elements in order to leave the list sorted, that is, in any case it will be necessary to go through the entire list, at least once.
Best case:
If the list is already sorted then no swap will be made, then we would have the best case, where we would have to compare the values at position 0, position 1, 2,..., n-2, up to n-1, since all values in its positions are smaller than its successor neighbor, there would be no exchange, and we would only loop over the list, so in a list of n elements we would have a total of n-1, comparisons, for the Big O notation, we disregard the term -1, Then we will have, for the best case: O(n).
Worst case scenario:
Bubblesort has its worst case when the list is in reverse order, in this case, in the initial loop the item that was at position 0 will end at position n-1, let's look at 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 largest value in the list to position n-2 in 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 ordered and the algorithm will still make one more loop before 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 non-dominant terms, and we will have: O(n²)