Why do I have an Infinite loop in bubble sort algorithm?

Yash Mehta 0
Viewed 44

The following code is where I face errors:

array = [16,1,2,3,4,5]
n = len(array)

swapped = True

while swapped == True:
    swapped = False
    for inner_index in range(1,n):
        first_number = array[inner_index - 1]
        second_number = array[inner_index]
        if first_number > second_number:
            first_number, second_number = second_number, first_number
            swapped = True
print(array)

This above code results in an infinite loop. Checking with python tutor, I noticed that it swaps the element but doesn't really "update" it in my array.

However, when I do the following, my code seems to be running:

Optimized Bubble sort algorithm code

array = [16,1,2,3,4,5]
n = len(array)

swapped = True #Dont forget boolean values start with a capital letter

while swapped == True:
    swapped = False
    for inner_index in range(1,n):
        if array[inner_index - 1] > array[inner_index]:
            array[inner_index - 1], array[inner_index] = array[inner_index], array[inner_index-1]
            swapped = True
print(array)

What's the difference between the two?

data-structures algorithm python
2 Answers

In the first code, you are updating the value of a variable, and then not assigning it back to the list. In the second example, you are directly assigning an element in the list to the value you want.

Change this line (in the first code):

first_number, second_number = second_number, first_number

To:

array[inner_index - 1], array[inner_index] = second_number, first_number
useroPDK0 
first_number = array[inner_index - 1]

Here, first_number is just referencing the value from the array. If you reassign first_number, it's value won't automatically update in the array (since it's not a pointer to the specific memory location).

In the second approach, the values are updated directly into the array, so it reflects the correct result.

Abhinav Mathur0
Related