Why Is Bubble Sort Implementation Looping Forever

Why is Bubble Sort implementation looping forever?

To explain why your script isn't working right now, I'll rename the variable unsorted to sorted.

At first, your list isn't yet sorted. Of course, we set sorted to False.

As soon as we start the while loop, we assume that the list is already sorted. The idea is this: as soon as we find two elements that are not in the right order, we set sorted back to False. sorted will remain True only if there were no elements in the wrong order.

sorted = False  # We haven't started sorting yet

while not sorted:
    sorted = True  # Assume the list is now sorted
    for element in range(0, length):
        if badList[element] > badList[element + 1]:
            sorted = False  # We found two elements in the wrong order
            hold = badList[element + 1]
            badList[element + 1] = badList[element]
            badList[element] = hold
    # We went through the whole list. At this point, if there were no elements
    # in the wrong order, sorted is still True. Otherwise, it's false, and the
    # while loop executes again.

There are also minor little issues that would help the code be more efficient or readable.

• In the for loop, you use the variable element. Technically, element is not an element; it's a number representing a list index. Also, it's quite long. In these cases, just use a temporary variable name, like i for "index".

  for i in range(0, length):
  

• The range command can also take just one argument (named stop). In that case, you get a list of all the integers from 0 to that argument.

  for i in range(length):
  

• The Python Style Guide recommends that variables be named in lowercase with underscores. This is a very minor nitpick for a little script like this; it's more to get you accustomed to what Python code most often resembles.

  def bubble(bad_list):
  

• To swap the values of two variables, write them as a tuple assignment. The right hand side gets evaluated as a tuple (say, (badList[i+1], badList[i]) is (3, 5)) and then gets assigned to the two variables on the left hand side ((badList[i], badList[i+1])).

  bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]
  

Put it all together, and you get this:

my_list = [12, 5, 13, 8, 9, 65]

def bubble(bad_list):
    length = len(bad_list) - 1
    sorted = False

    while not sorted:
        sorted = True
        for i in range(length):
            if bad_list[i] > bad_list[i+1]:
                sorted = False
                bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]

bubble(my_list)
print my_list

(I removed your print statement too, by the way.)

Why is the range loop in bubble sort reversed?

In your code, the index i is the largest index that the inner loop will consider when swapping the elements. The way bubble sort works is by swapping sibling elements to move the largest element to the right.

This means that after the first outer iteration (or the first full cycle of the inner loop), the largest element of your list is positioned at the far end of the list. So it’s already in its correct place and does not need to be considered again. That’s why for the next iteration, i is one less to skip the last element and only look at the items 0..len(lst)-1.

Then in the next iteration, the last two elements will be sorted correctly, so it only needs to look at the item 0..len(lst)-2, and so on.

So you want to decrement i since more and more elements at the end of the list will be already in its correct position and don’t need to be looked at any longer. You don’t have to do that; you could also just always have the inner loop go up to the very end but you don’t need to, so you can skip a few iterations by not doing it.

---

I asked why we are going reverse in the list like len(list)-1,0. Why are we not going forward way like 0,len(list)-1?

I was hoping that the above explanation would already cover that but let’s go into detail. Try adding a print(i, alist) at the end of the outer loop. So you get the result for every iteration of i:

>>> bubbleSort([5, 1, 3, 9, 2, 8, 0])
6 [1, 3, 5, 2, 8, 0, 9]
5 [1, 3, 2, 5, 0, 8, 9]
4 [1, 2, 3, 0, 5, 8, 9]
3 [1, 2, 0, 3, 5, 8, 9]
2 [1, 0, 2, 3, 5, 8, 9]
1 [0, 1, 2, 3, 5, 8, 9]

As you can see, the list will be sorted from the right to the left. This works well for our index i which will limit how far the inner loop will go: For i = 4 for example, we already have 3 sorted elements at the end, so the inner loop will only have to look at the first 4 elements.

Now, let’s try changing the range to go in the other direction. The loop will be for i in range(0, len(alist)). Then we get this result:

>>> bubbleSort([5, 1, 3, 9, 2, 8, 0])
0 [5, 1, 3, 9, 2, 8, 0]
1 [1, 5, 3, 9, 2, 8, 0]
2 [1, 3, 5, 9, 2, 8, 0]
3 [1, 3, 5, 9, 2, 8, 0]
4 [1, 3, 5, 2, 9, 8, 0]
5 [1, 3, 2, 5, 8, 9, 0]
6 [1, 2, 3, 5, 8, 0, 9]

As you can see, this is not sorted at all. But why? i still limits how far the inner loop will go, so at i = 1, the loop will only look at the first pair and sort that; the rest will stay the same. At i = 2, the loop will look at the first two pairs and swap those (once!); the rest will stay the same. And so on. By the time the inner loop can reach the last element (which is only on the final iteration), there aren’t enough iterations left to swap the zero (which also happens to be the smallest element) to the very left.

This is again because bubble sort works by sorting the largest elements to the rightmost side first. So we have to start the algorithm by making the inner loop be able to reach that right side completely. Only when we are certain that those elements are in the right position, we can stop going that far.

There is one way to use a incrementing outer loop: By sorting the smallest elements first. But this also means that we have to start the inner loop on the far right side to make sure that we check all elements as we look for the smallest element. So we really have to make those loops go in the opposite directions.

Why is my bubble sort algorithm implementation sorting the entire array and skips the first index?

Why ... skips the first index?

Because you set i = 0 inside the loop, but then the loop will do i++, so the first element is only examined on the first iteration, not on any "restart".

To restart correctly, use i = -1 so the i++ will make restart happen at i = 0, not at i = 1.

That will make the code work, but it is inefficient to restart immediately upon swapping two elements, because you will repeatedly recheck the beginning of the array.

JavaScript bubble sort modification (Looping `i` stops before the sorting ends.)

var swap = true;
for (var i = 0; (i < n) && (swap === true); ++i) {
    swap = false;
    for (var j = 0; j < ( n - (i + 1) ); ++j) {
        if ( arr[j] > arr[j + 1] ) {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;

            swap = true;
        }
    } 
}

Once loopi didn't swap any number, "swap" will be false, then we can exit the loop.

MASM611 - Bubble Sort giving unexpected output

ARRAY DB 59H, 39H, 51H, 57H, 24H, 86H, 95H, 93H, 15H, 75H, 42H, 68H, 03H, 06H, 01H

When dealing with this array of bytes, you have to decide how these bytes need to be interpreted.

You can deal with them in the unsigned manner where their values will range from 0 to 255, or you can deal with them in the signed manner where their values will range from -128 to +127. Your code snippet uses the jl (JumpOnLess) instruction which tells us that you (knowingly?) prefer the signed manner. Because values like 86h, 95h, and 93h represents negative numbers (when viewed as signed numbers), this ascending sort will place these first.

If you wish to sort an array of unsigned numbers then just use the jb (JumpOnBelow) instruction.

---

One optimization for your BubbleSort

The inner loop can start from an ever smaller counter because the last element from the current iteration will have reached its final destination.

Change:

OLOOP:
    MOV CX, COUNT-1

into

OLOOP:
    MOV CX, DX

bubble sort algorithm for loop statement warning

The result of an assignment is the left operand, so the condition

sorted = !sorted

is using sorted as the condition after it's assigned a new value. The warning is there to give you a notice that using assignment as condition is sometimes not what you expected. You can use

(sorted = !sorted) == true

to silence the warning.

---

Related Topics