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.
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.