I would like to keep track of bubble sorting algorithm’s intermediate states at each iteration. I’ve tried to cache them in dictionary while loop is running, but i keep getting the same state all the time
Here is my code:
def bubblesort(lst): cache = {} # Swap the elements to arrange in order iter = 0 for iter_num in range(len(lst)-1,0,-1): new_lst = lst for idx in range(iter_num): iter += 1 if new_lst[idx]>new_lst[idx+1]: new_lst[idx], new_lst[idx+1] = new_lst[idx+1], new_lst[idx] cache[f'iter{iter}'] = new_lst return cache
Here is the output:
{'iter1': [50, 119, 194, 365, 608, 788, 851, 879, 960], 'iter2': [50, 119, 194, 365, 608, 788, 851, 879, 960], 'iter3': [50, 119, 194, 365, 608, 788, 851, 879, 960], 'iter4': [50, 119, 194, 365, 608, 788, 851, 879, 960], 'iter5': [50, 119, 194, 365, 608, 788, 851, 879, 960], 'iter6': [50, 119, 194, 365, 608, 788, 851, 879, 960], 'iter7': [50, 119, 194, 365, 608, 788, 851, 879, 960], 'iter8': [50, 119, 194, 365, 608, 788, 851, 879, 960], 'iter9': [50, 119, 194, 365, 608, 788, 851, 879, 960], 'iter10': [50, 119, 194, 365, 608, 788, 851, 879, 960], ...}
As you can see, it outputs sorted list each time. What am I missing here?
Advertisement
Answer
The problem is, that with the line
cache[f'iter{iter}'] = new_lst
both the object in the cache dictionary as well as the new_list variable point to the same object.
In the next interation then
new_lst = lst
overwrites it with a new object and now the cache, lst and new_list point to the same object.
What you need to do, is to create a ‘real’ copy of the object. For that you can use the copy
package.
You should also read about the difference between shallow and deep copy
as they are very fundamental and the source of a multitude of problems if not understood correctly.
from copy import copy [...] cache[f'iter{iter}'] = copy(new_lst)