Quick Sort using Python

Question

I was wondering if someone can help me to fix the error my code for quick sort has: It does not compile and highlights the last line of the code in red. I can not figure out what is wrong. sort is already defined as a function so why is it highlighted as red?

def sort(*myarray):
    less = []
    equal = []
    greater = []

    if len(myarray) > 1:
        pivot = myarray[0]
        for x in myarray:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
        return sort(less)+sort(equal)+sort(greater)
    else:
        return myarray
print sort([12,4,5,6,7,3,1,15])

this runs when I try it but doesn't work as desired - it simply returns a tuple `([12,4,5,6,7,3,1,15],)` — Stuart, Aug 15 '13 at 22:48

score 4 · Accepted Answer · edited May 23 '17 at 10:31

You're defining the function as taking a variable number of arguments (the *myarray bit), but then using myarray inside as a single argument (the list to sort), when it is a list containing the list to sort.

You probably should remove the * from your function parameter. This questions esplains it quite thoroughly.

You could keep the *, but then you would have to play a bit with tuple unpacking to get the same result.

edit

Although the above is true, this might not be the issue you're encountering.

IDLE will give you the invalid syntax error on the ast line, because in interactive mode - with lines starting with >>>, it accepts only one statement at a time. In your case that statement is the sort() definition.

Try hitting enter 2 times after the function definition, this should get you back to the repl, where you can introduce another statement (print sort([12,4,5,6,7,3,1,15]))

I can confirm it works when you do this, but as @amit points out it recurses infinitely if there are equal elements in the list. — Stuart, Aug 15 '13 at 22:51
Thank you for your help. I did remove the * . For some reason on my computer it still does not work and highlights the last line of the code red and says: syntax error. I am using IDLE. Using an online compiler it works fine. — user2687481, Aug 15 '13 at 23:01

score 2 · Answer 2 · answered Aug 15 '13 at 22:51

There are a couple things wrong which makes me curious how you are testing this:

Python code is not "compiled", it is interpreted. (Okay, not precisely true; it's parsed into a sort of byte-code; still, it's not compiled in the same sense as a language such as C, where the entire program has to be converted into machine instructions before any of it can be run.) Also you mention the last line of code is highlighted in red -- by what?
This code actually works, but only if you remote the star/asterisk in front of myarray in def sort(*myarray):. Otherwise it actually returns a single-element tuple containing the original array.

Possible answer to #1 above: you are using some sort of IDE that has detected the inconsistency of declaring `sort` as taking a variable number of arguments, and then passing it a whole list as a single argument instead. — Richard Walters, Aug 15 '13 at 22:54

score 0 · Answer 3 · answered Aug 15 '13 at 22:48

Assuming you have two or more elements that equal a pivot at some point, you get an infinite loop, because you will get: equal = [x,x] (two elements at least), and then invoke sort([x,x]), which in its turn will take x as a pivot, and create equal = [x,x], and cause sort([x,x]), ....

Simple solution to this problem: What should be the output of the sort(equal)? How do you sort a list of identical elements?

Edit: Well, your comments show that you are looking for a different problem, but I'll leave it here because it explains a different issue you have with your code and should be solved.

Thank you for you tip. I fixed it by replacing sort(equal) with equal — user2687481, Aug 16 '13 at 04:28

score 0 · Answer 4 · answered Jul 06 '14 at 01:22

If it is a function for quick sorting, can you really use the function sort in it?

Wouldn't something like this work?

def qsort(list):
    pivind=0 
    left, right, pivot= [], [], []
    for x in list:
        if list[pivind]==x: pivot.append(x)
        elif list[pivind]>x: left.append(x)
        else: right.append(x)

    if len(left)>1: left=qsort(left)
    if len(right)>1: right=qsort(right)
    return (left + pivot + right)

Quick Sort using Python

4 Answers4