sorting list by swapping adjacent elements

Question

By trial and error i've got the solution to do this but i don't understand why it works.

n=input()
f=n.split(' ')
count = 0

while count <  ( len(f) * (len(f)-2) ):
    
    for z in range(1, len(f)):
       
        if int(f[z]) > int(f[z-1]):
            f[z], f[z-1] = f[z-1], f[z]
       
        if int(f[z]) < int(f[z-1]):
            count +=1
            
print (f)

so i started out with just while count < len(f) in line 5 and soon understood why it wouldn't work, i tried different multiples of len(f) and soon came to the conclusion len(f) * (len(f)-2) is the par to which i need to check, it does work with all values above it for example len(f) **2

i'm just a beginner and don't understand it only works for len(f) * (len(f)-2) exactly and above. could someone kindly explain it as simply as possible thank you.

Answer 1

For context, you may wish to review big O notation: a good starting point can be found here (try Wikipedia for a more formal explanation). I will explain why without requiring knowledge of this notation however.

Your code is an implementation of bubble sort, which has a worst case time complexity of n squared (O(n^2) in big O notation), where n is the length of the list. This means that in the worst case, it will take a time proportional to the length of the list squared to complete. This is best explained by looking at the worst case scenario of a list reverse sorted.

The following grepper answer implements bubble sort:

# Credit to: https://www.grepper.com/profile/wissam-fawaz
def bubble_sort(array):
    isSorted = False
    passes = 0
    length = len(array)
    while not isSorted:
        isSorted = True
        # perform a pass through the array
        # excluding already sorted positions
        for i in range(length-1-passes):
            if array[i] > array[i+1]:
                swap(i, i+1, array)
                # array is not sorted yet
                isSorted = False
        passes += 1
    return array

def swap(i, j, array):
    # Swap values at indexes i and j
    array[i], array[j] = array[j], array[i]

This algorithm will loop through the reverse sorted list, at each point shuffling the smallest number to the bottom. For example, for the list [4, 3, 2, 1]:

Iteration 1:
[3, 2, 1, 4]

Iteration 2:
[2, 1, 3, 4]

Iteration 3:
[1, 2, 3, 4]

Iteration 4 (checking):
[1, 2, 3, 4]

As you can see, we've gone through the while loop 4 times, and the inner for loop has iterated through each element in the list at every loop in the while loop, resulting in the worst case time complexity of n squared.

Your algorithm's count counts the number of swaps made. This number will therefore be proportional to the square of the length of the list in the worst case.