Sort color problem

Python Help
1

Hi,

Could you comment my answer to the question? Thanks!

Question:
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

This is my solution which I can’t see any wrong with, but the system does not let me pass.

 class Solution:
     def sortColors(self, nums: List[int]) -> None:
         """
         Do not return anything, modify nums in-place instead.
         """
         from collections import Counter
         d1 = Counter(nums)
         nums = [0]*d1[0] +[1]*d1[1] +[2]*d1[2]

I know my solution is a short cut which is not the test maker intended me to take, but I do not see any coding mistake. In particular, the system believes I fail in this test case:

Your input
[2,0,2,1,1,0]
Output
[2,0,2,1,1,0]
Expected
[0,0,1,1,2,2]

I believe my code should yield [0,0,1,1,2,2] . Could anyone pinpoint my problem?

2

When you type nums = [some list], this doesn’t modify the list in place, it merely creates a "new* list and binds it to the name nums. Anyone still holding a reference to the old list does not see the change. What you probably want is nums[:] = [some list], which replaces the contents of nums, in-place.

Compare:

A = [1, 2]
B = A
print(A is B) # True
B = [3, 4]
print(A is B) # False, not the same list
print(A, B)
# prints [1, 2] [3, 4]

C = [5, 6]
D = C
print(C is D) # True
D[:] = [7, 8]
print(C is D) # True, still the same list, just modified in place.
print(C, D)
# prints [7, 8] [7, 8]
1 Like
3

Thank you. Is it because the list “nums” is one argument of the function, so " nums = [some list]" does not modify the list?

I do the same thing when “a” is not an argument in the function, and “a = [some list]” does modify the list

a = [3,4,5]
a
[3, 4, 5]
a = [5,6]
a
[5, 6]
4

This is homework, so I don’t believe that using Counter is encouraged or allowed. I believe that aim is to make you implement some sorting algorithm - for example bubble sort. Algorithm in natural language is pretty simple and translating it into Python shouldn’t be a problem:

Bubble sort repeatedly steps through the list to be sorted,
compares each pair of adjacent items and swaps them if they are
in the wrong order. The pass through the list is repeated until
loop is exhausted.

As n-th pass finds the n-th largest element and puts it into
its final place algorithm implements inner loop optimization i.e.
inner loop is not handling n - 1 item and beyond  when running for n-th time.

Algorithm can implement change flag for
determing whether adjacent items are swapped during pass.
The pass through the list is repeated until no swaps are needed,
which indicates that the list is sorted. In this case code will
break out from outer for-loop.
1 Like
5

No, the situation is the same regardless of the context (and in a broader sense, regardless of what type of variable you’re dealing with). In Python, there are no value types vs. reference types, and no pass-by-reference vs. pass-by-value. Rather, every variable value is an object, every variable name a reference to an object, and there is a crucial distinction between the two—i.e., a given name, and the thing that name currently refers to.

Consider, for example, the goalkeeper of a sports team. The name “goalkeeper”, in the context of that team (i.e. that scope), refers to one given person, say, Alan, at a particular given time. However, let’s say Alan was injured while playing, and another person, Bob, was assigned to be new goalkeeper (i.e. to that name).

If we now look up to see who the “goalkeeper” is, we are now told it is Bob. However, if we know Alan by another name (for example, let’s say they are also the team captain), that name still refers to Alan, not Bob (unless we re-assign that too). Also, Bob doesn’t inherit Alan’s injury, statistics or other attributes just because he was named goalkeeper in Alan’s place, and neither does anything that happen to him as goalkeeper affect Alan.

In code, we can represent the situation something like this:

alan = Player("Alan")
bob = Player("Bob")

goalkeeper = alan
captain = alan
goalkeeper.injure()
goalkeeper = bob

assert goalkeeper is bob
assert captain is alan
assert alan.injured
assert not bob.injured

Applying this to your situation. you have a list object, [3, 4, 5], that you’ve given the name a. If you then create a new list object [5, 6] and assign that new object to the name a, what the name refers to changes (like who was currently called the goalkeeper), but the original list object (like Alan, the person who was original goalkeeper) doesn’t change simply by giving something else that name. If you also knew the list a by another name, say original_list in

original_list = [3, 4, 5]
a = original_list
a = [5, 6]

then original_list (like the team captain) doesn’t change just because you reassigned another object to a (like another person to goalkeeper).

If you instead modify the original object, i.e.

a[:] = [5, 6]

just like injuring a goalkeeper, you’re modifying the object itself in place, not just what is assigned to its name, and so other names for that object (like original_list) will reflect those changes.

Actually no, it doesn’t modify the list, as you’ve now learned. Rather, it creates a new list object, and then assigns it the same name as the previous one. Does that make sense now?

1 Like
6

Aivar suggested:

“This is homework, so I don’t believe that using Counter is encouraged or allowed.”

Then they should have been more clear about the requirements.

Given the requirements as stated, counting the values as John did solves the problem, and more efficiently than using something as bad as bubblesort.

Besides, if you’re going to write a terrible sort algorithm, do it right wink I see your O(N**2) bubblesort and raise you O(N!) Bozosort:


# Untested. This may contain typos or errors.
import random

def bozosort(alist):
    def issorted():
        for i in range(1, len(alist)):
            if alist[i-1] > alist[i]:
                return False
        return True
    while not issorted():
        i = random.randrange(len(alist))
        j = random.randrange(len(alist))
        # Swap the elements.
        alist[i], alist[j] = alist[j], alist[i]

For the record, this is not even close to the worst known sorting algorithm.

2 Likes
7

Well said, of course. I ended up not addressing this myself above, but at least as an atmospheric scientist and developer rather than computer scientist or engineer, I am less interested in the student learning a particular algorithm to solve this particular problem as opposed to a meta-algorithm used to derive solutions to any problem. In the latter aspect, at least, I would commend a student thinking outside the box and devising a less obvious but much shorter, simpler and more efficient solution given the constraints of the problem (which is how clever optimizations are born), rather than rebuking them for not using the approach I’d intended them to.

Furthermore, I would (and did) see their confusion over a different point as an excellent opportunity to teach them a much more fundamental concept (objects, names and the distinction between them) that permeates not only all of Python, but also helps understand other languages too, and why they act differently, as well as provides a conceptual framework to think about what’s actually happening under the hood beyond the mere tokens in a file.