This may be the weirdest problem I've ever seen, when I set the object at index 3 (the 4th object) to 5, the bubble sort algorithm seems to have problems, but when I set it to 12, the problem goes away, even though both 12 and 5 are lower numbers than both the numbers at index 2 and 4 (the numbers before and after 5/12) Here's the code, and here's the output:
array_to_sort = [10, 5, 13, 5, 42]
should_stop = False
print(array_to_sort)
while should_stop == False:
should_stop = True
index = 1
for back_number in array_to_sort:
print(array_to_sort)
front_number = array_to_sort[index]
if back_number > front_number:
array_to_sort.remove(back_number)
array_to_sort.remove(front_number)
array_to_sort.insert(index - 1, front_number)
array_to_sort.insert(index, back_number)
should_stop = False
if index + 1 < len(array_to_sort):
index += 1
(obviously not all the output):
[10, 5, 13, 5, 42]
[10, 5, 13, 5, 42]
[5, 10, 13, 5, 42]
[5, 10, 13, 5, 42]
[10, 5, 5, 13, 42]
[10, 5, 5, 13, 42]
However, it does eventually get fully sorted
Then with the same code, but if I set the array to this:
array_to_sort = [10, 5, 13, 12, 42]
The output becomes what would be expected:
[10, 5, 13, 12, 42]
[10, 5, 13, 12, 42]
[5, 10, 13, 12, 42]
[5, 10, 13, 12, 42]
[5, 10, 12, 13, 42]
[5, 10, 12, 13, 42]
PS: I know this is definitely not the best way to do bubble sort, I'm just starting with python.
This will happen any time there are duplicates in your list. list.remove removes the first instance of the object being removed. So when you try to remove the second 5 at index 3, you're actually removing the 5 at index 1.
Solution? Don't use list.remove in this scenario. Just swap the two values. This will be easiest if you use a loop over a range.
for back_number in range(len(array_to_sort)-1):
print(array_to_sort)
front_number = array_to_sort[back_number+1]
if array_to_sort[back_number] > array_to_sort[front_number]:
array_to_sort[front_number],array_to_sort[back_number] = array_to_sort[back_number], array_to_sort[front_number]
should_stop = False