Python Bubble Sort - False flag-CodePudding

I have this situation on a bubble sort script in Python 3:

my_list = [8, 10, 6, 2, 4]  # list to sort
swapped = True

while swapped:
    swapped = False
    for i in range(len(my_list) - 1):
        if my_list[i] > my_list[i   1]:
            swapped = True  # a swap occurred!
            my_list[i], my_list[i   1] = my_list[i   1], my_list[i]

print(my_list)

I don't understand swapped = False inside the while loop, don't should break my while loop instead of flagging the list's elements?

I have tried to put an else clause:

my_list = [8, 10, 6, 2, 4]  # list to sort
swapped = True  # It's a little fake, we need it to enter the while loop.

while swapped:
    swapped = False  # no swaps so far
    for i in range(len(my_list) - 1):
        if my_list[i] > my_list[i   1]:
            swapped = True  # a swap occurred!
            my_list[i], my_list[i   1] = my_list[i   1], my_list[i]
        else:
            print("No swap")

print(my_list)

But the output shows me:

No swap
No swap
No swap
No swap
No swap
No swap
No swap
No swap
[2, 4, 6, 8, 10]

Thank you for your support.

CodePudding user response：

Your code works perfectly fine. In your situation, the while loop replaces the standard double for loop used in bubble sort. To rewrite your code to bubble sort, it would look like this:

my_list = [8, 10, 6, 2, 4]  # list to sort

for _ in range(len(my_list)-1):
    for i in range(len(my_list) - 1):
        if my_list[i] > my_list[i   1]:
            my_list[i], my_list[i   1] = my_list[i   1], my_list[i]
print(my_list)

So, what is going on here? In bubble sort, you iterate over a list of n elements, n-1 times. For each pair adjacent pair, if they are not sorted, you sort them by swapping them. In the best scenario, you need 0 iterations through the list to sort them, hence a sorted list. In the worst scenario, you need n-1 times to sort all the list. That is, when the minimum value of your list is placed at the end. It has to make all n-1 swaps in order to get to the position it is supposed to be in: the first.

Now, why does your code work the way it works and why is it more optimal. See, the approach the standard bubble sort uses, it is always based on the worst case scenario. Even if your list is sorted sooner than n-1 iterations, it still goes over it to check if any swaps are needed. That is where your code is more efficient. Once there are no swaps left, you stop the iteration process and return the sorted list. It breaks out of the while loop after the minimal required iterations to sort the list.

As tadman already pointed out though, this is a suboptimal sorting method that does not need optimizing. Bubble sort is a slow method, with a complexity of O(n*n). You are now reducing the complexity to O(minimal iterations * n), but this is still O(n*n).

CodePudding user response：

While the code is not particularly efficient it does work.

The first swapped = True assignment before the while loop obviously initializes the variable so that the while loop runs.

The second assignment, swapped = False sets up a situation where an assumption is made that no more swaps are possible and therefore the loop is to be exited.

The execution then proceeds to the for loop where that assumption is tested. If any swap occurs, the sorting procedure is deemed to be unfinished and should therefore continue the while loop as more swaps are possible. In order to make this happen, the swapped variable is set to True as this is what the logic condition of the while loop will test and so you see the third assignment swapped = True.

Hope this clears things up bit