How to properly copy a list in python

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?

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)