4
\$\begingroup\$
import random

def qsort(qslist):

    small = []
    big = []

    if (len(qslist) < 2):
        return qslist

    elif (len(qslist) > 1):

        pivot = qslist[int(random.randrange(len(qslist)))]

        for x in range(len(qslist)):
            if qslist[x] <= pivot:
                small.append(qslist[x])
            else:
                big.append(qslist[x])
        if(len(big) == 0):
            big.append(pivot)
            small.remove(pivot)

return qsort(small) + qsort(big)

qslist = [9,1,8,2,7,3,6,4,5]
print(qsort(qslist))

Please give me advice while picking up Python. I'm trying to do so while at the same time doing some basic algorithms.

  1. Have I understood how the quicksort algorithm work?
  2. Please give me some general feedback on the Python code.
\$\endgroup\$
2
\$\begingroup\$

Some comments:

  • Write docstrings to document code
  • Use if/else instead of if/elif if possible
  • Use list comprehensions
  • Use random.choice to get a random element from a non-empty sequence

The code in the original questions with the suggested improvements would be as follows:

import random

def qsort(qslist):
    """"Quicksort implementation."""
    if len(qslist) < 2:
        return qslist

    pivot = random.choice(qslist)
    small = [x for x in qslist if x < pivot]
    equal = [x for x in qslist if x == pivot]
    big = [x for x in qslist if x > pivot]

    return qsort(small) + equal + qsort(big)

qslist = [9,1,8,2,7,3,6,4,5]
print(qsort(qslist))

Edit: If you prefer to avoid traversing the array three times, a partition function to do that very similar to the one in the original question would be:

def partition(qslist):
    """Partition array using a pivot value."""
    small = []
    equal = []
    big = []

    pivot = random.choice(qslist)
    for x in qslist:
        if x < pivot:
            small.append(x)
        elif x == pivot:
            equal.append(x)
        else:
            big.append(x)

    return small, equal, big
\$\endgroup\$
10
  • \$\begingroup\$ Hello, thanks for your reply, but i wonder if your code works if the list contains several of the "same" items, it dosent seem todo. Chane the list to contain several "1" to se what i mean. \$\endgroup\$
    – macbug
    Aug 6 '14 at 10:52
  • \$\begingroup\$ Thanks for your comment. The code indeed failed in the case of repeated values, I've updated it to take that into account. \$\endgroup\$
    – jcollado
    Aug 6 '14 at 10:59
  • \$\begingroup\$ Great, i need to do a bit more of list compehensions! :) \$\endgroup\$
    – macbug
    Aug 6 '14 at 11:11
  • \$\begingroup\$ Note that I used list comprehensions for readability, but you can still define your own partition function to do just one pass over qsist which would be more efficient. \$\endgroup\$
    – jcollado
    Aug 6 '14 at 11:13
  • 1
    \$\begingroup\$ @miR What I suggest is if/else over if/elif when the condition in the elif is exclusive and, hence, not needed. \$\endgroup\$
    – jcollado
    Aug 7 '14 at 7:27
2
\$\begingroup\$

A few comments, not so much about the algorithm as it has be done pretty well already but more about the code itself :

  • your return does not seem properly indented.
  • you should put your test (or basically any code actually doing something) behind a main guard.
  • there is no point in checking if the length is bigger than 1 after you've checked that it is not smaller than 2. If you really want to, you can add an assert.
  • you can (and should) define big and small as late as possible : we will only need them in the else case, this is where it belongs.
  • the way you loop over the list is not pythonic at all. You should see the for loop as a for-each loop and use it as such. It makes things easier to read/write, it is shorter, it is more efficient and it will be easier to re-use if you have to work on different iterables.
  • you could put your return in the else block or you could get rid of the else block alltogether as your return in the then block.

After taking into account these simple comments, here is what I have :

import random

def qsort(qslist):

    if len(qslist) < 2:
        return qslist

    assert len(qslist) > 1
    pivot = random.choice(qslist) 

    small = []
    big = []

    for x in qslist:
        if x <= pivot:
            small.append(x)
        else:
            big.append(x)
    if len(big) == 0:
        big.append(pivot)
        small.remove(pivot)

    return qsort(small) + qsort(big)

def main():
    """Main function"""
    print("Hello, world!")
    qslist = [9, 1, 8, 2, 7, 3, 6, 4, 5] * 200
    print(qsort(qslist))


if __name__ == "__main__":
    main()
\$\endgroup\$
0
1
\$\begingroup\$

Yes, the algorithm looks like quicksort.

There are only two things I would have done differently:

  1. Why do you randomly generate a number within the range of the list to pick the corresponding element? Just randomly pick an element from the list:

    pivot = random.choice(qslist)
    
  2. Why do you generate sequential indices to pick all elements of your list? Just sequentially pick all elements: for value in qslist: ...

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.