Dictionary does not update specific values and instead returns the same value in all the spots

Question

I'm creating a bubble sort algorithm that takes a list and returns 2 values: 1st returned value: a dictionary with the state of the list after each complete pass of bubble sort 2nd returned value: the sorted list

    log = {}

    for n in range(len(numList)):
        for i in range(0, len(numList)-n-1):
            # Comparing numbers and swapping them
            if numList[i] > numList[i+1]:
                numList[i], numList[i+1] = numList[i+1], numList[i]
            # Creating log of the state of each pass
            log[n+1] = numList
        # Returning Results
        return log, numList

Sample Input: >>> bubbleSort([9,3,5,4,1,67,78])

Sample Output: ({1: [3, 5, 4, 1, 9, 67, 78], 2: [3, 4, 1, 5, 9, 67, 78], 3: [3, 1, 4, 5, 9, 67, 78], 4: [1, 3, 4, 5, 9, 67, 78], 5: [1, 3, 4, 5, 9, 67, 78]}, [1, 3, 4, 5, 9, 67, 78])

Possible duplicate of [List of lists changes reflected across sublists unexpectedly](https://stackoverflow.com/questions/240178/list-of-lists-changes-reflected-across-sublists-unexpectedly) — Thierry Lathuille, Apr 05 '19 at 18:40

Cohan · Answer 1 · 2019-04-05T19:12:39.837

Assuming the indentation is matching what you have in your actual file, you are returning the result after the inner loop completes it's first run. Try de-denting it. Also, add the .copy() method to the list. You have to use the .copy() method to capture the state. Otherwise, you will have a list of elements all pointing to the same element that is being constantly updated.

def foo(numList):

    log = {}

    for n in range(len(numList)):
        for i in range(0, len(numList)-n-1):
            # Comparing numbers and swapping them
            if numList[i] > numList[i+1]:
                numList[i], numList[i+1] = numList[i+1], numList[i]
            # Creating log of the state of each pass
            log[n+1] = numList.copy() # add the .copy()
    # Returning Results
    return log, numList # ensure proper indentation

print(foo([4, 0, 2, 3, 1]))

Output

({  1: [0, 2, 3, 1, 4], 
    2: [0, 2, 1, 3, 4], 
    3: [0, 1, 2, 3, 4], # a lot of stuff happened to get here
    4: [0, 1, 2, 3, 4]  # list was already in order, so this is repeated
    }, 
    [0, 1, 2, 3, 4])

If you are trying to debug/verify that your sort is working, I'd suggest using a list and appending a copy of the state of the array. The steps are preserved since a list is ordered while a dictionary is not.

Also, be mindful with your indentation and where you want to capture the data. putting the log in the if statement will provide a change whenever there IS a change. As a child of the second loop, you'll have entries even if changes don't occur, and then the top loop won't capture all the changes.

def foo(numList):

    log = [] # Change to list for a list of lists

    for n in range(len(numList)):
        for i in range(0, len(numList)-1-n):
            if numList[i] > numList[i+1]:
                numList[i], numList[i+1] = numList[i+1], numList[i]

                log.append(numList.copy()) # Append a copy

    return log, numList

print(foo([4, 0, 2, 3, 1]))

Output:

([[0, 4, 2, 3, 1], 
  [0, 2, 4, 3, 1], 
  [0, 2, 3, 4, 1], 
  [0, 2, 3, 1, 4],
  [0, 2, 1, 3, 4],
  [0, 1, 2, 3, 4]], 

 [0, 1, 2, 3, 4])

It's also worth mentioning that you probably don't want the logging feature in there for any production runs. I assume this is an academic exercise. On smaller lists, it's not a problem, but if you sort large lists, you could run into memory issues.

Dictionary does not update specific values and instead returns the same value in all the spots

1 Answers1