Welcome to the Treehouse Community

The Treehouse Community is a meeting place for developers, designers, and programmers of all backgrounds and skill levels to get support. Collaborate here on code errors or bugs that you need feedback on, or asking for an extra set of eyes on your latest project. Join thousands of Treehouse students and alumni in the community today. (Note: Only Treehouse students can comment or ask questions, but non-students are welcome to browse our conversations.)

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and a supportive community. Start your free trial today.

Computer Science

ilker senturk
ilker senturk
17,583 Points

quick sort in python

when run the method, it seems work but if we rerun loosing an element in the list,

def quickSort(sequence):

    length = len(sequence)
    if(length <= 1):
        return sequence
    else:
        pivotPoint = sequence.pop()
        items_greater = []
        items_lower = []

        for item in sequence:
            if item > pivotPoint :
                items_greater.append(item)
            else:
                items_lower.append(item)

    return quickSort(items_lower) + [pivotPoint] + quickSort(items_greater) 
Chris Freeman
Chris Freeman
Treehouse Moderator 67,636 Points

Can you please expand on what you mean by "if we rerun loosing an element in the list"?

2 Answers

Chris Freeman
MOD
Chris Freeman
Treehouse Moderator 67,636 Points

The issue is caused by the pop() in

        pivotPoint = sequence.pop()

Python passes arguments by reference, so at the top level of recursion, the first pop actually pops an item off of the arr collection.

Because of this feature of python, it is best not to directly alter arguments unless explicitly understanding the side effects. Local assignment to a variable, make it "local" (a distinct copy of the argument). For example:

def somefunc(arr):
    first = arr[0]
    arr = arr[1:]  # arr is now local and external arr is unaffected

Another simple fix would be to use:

        pivotPoint = sequence[0]  # get the first item

and

        for item in sequence[1:]:   # sort excluding the first item

Post back if you need more help.

ilker senturk
ilker senturk
17,583 Points

when i call the method , it sorted the sequence , so the output for arr = [8, 7, 2, 5, 3, 1,12] will be [1, 2, 3, 5, 7, 8, 12] but if Call the method twice print(quickSort(arr))
print(quickSort(arr))

printing [1, 2, 3, 5, 7, 8] where i am loosing 12,

print(quickSort(arr))
print(quickSort(arr)) print(quickSort(arr))

printing [2, 3, 5, 7, 8] where i lost element 1 I couldn't get where i make a mistake