CODEWITHSUNDEEP
pythonfor-loopboolean
mindlessobject
mindlessobject

Reputation: 31

How to evaluate nested boolean values?

I'm relatively new to python and have gotten comfortable with the the basics, even nested for loops for example. I encountered the function below and when I tried to understand what it's doing, I got tripped up. It always returns the list that is passed through the function, and appears to assign a boolean value of False to to an element "x" based on the length of the list passed in, ultimately breaking the loop when the values of false aren't the case. What I don't understand is the role of the first element in the for loop, relative to the second for loop (it being subtracted from size). If any could help me better understand what this function is doing, it would be appreciated.

def myfunc(list):

    size = len(list)

    for x in range(0, size):
        foo = False

        for x2 in range(0, size - x - 1):
            if list[x2] > list[x2 + 1]:
                list[x2], list[x2 + 1] = list[x2 + 1], list[x2]
                foo = True

        if not foo: break

    return list

Upvotes: 3

Views: 199

Answers (1)

Polaris000
Polaris000

Reputation: 938

The function you have written is an implementation of a sorting technique known as bubble sort. It simply compares adjacent elements to sort the list.

Though you don't necessarily have to stop the second for loop at size - x - 1 iterations, it helps decrease the number of compares you perform, thus improving the efficiency of an algorithm already having a time complexity of the order of n ^ 2 which performs poorly on larger lists.

If you trace through the execution, you will realize that after every iteration of the outer loop, one more element reaches the exact place where it would be in the sorted array and its better not to consider that element in subsequent iterations.

Thus your program stops the inner loop early, knowing that the last x elements have already been sorted.

When it comes to the boolean, it further decreases the compares you perform. For example, when you pass in a sorted list: In the first iteration of the outer loop, x = 0. Then the inner loop iterates size - 1 times comparing adjacent elements but not performing the swap since the elements are already in order. Once the inner loop finishes all iterations for the first iteration of the outer loop (x = 0), its pointless to go with further iterations and its better to stop the algorithm at this point. The break statement ensures this happens.

Thus, in the best case, the time complexity of your algorithm would be the order of n (O(n)), which is better than the average or worst case complexity of O(n^2)

Upvotes: 1

Related Questions