Some comments:

• Write docstrings to document code
• Useif/else instead ofif/elif if possible
• Use list comprehensions
• Userandom.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 randomdef 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 partitionfunction 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

• \$\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

  – macbug

  2014-08-06 10:52:42 +00:00

  CommentedAug 6, 2014 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

  – jcollado

  2014-08-06 10:59:41 +00:00

  CommentedAug 6, 2014 at 10:59
• \$\begingroup\$Great, i need to do a bit more of list compehensions! :)\$\endgroup\$

  macbug

  – macbug

  2014-08-06 11:11:32 +00:00

  CommentedAug 6, 2014 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 overqsist which would be more efficient.\$\endgroup\$

  jcollado

  – jcollado

  2014-08-06 11:13:24 +00:00

  CommentedAug 6, 2014 at 11:13
• 1
  \$\begingroup\$@miR What I suggest isif/else overif/elif when the condition in theelif is exclusive and, hence, not needed.\$\endgroup\$

  jcollado

  – jcollado

  2014-08-07 07:27:24 +00:00

  CommentedAug 7, 2014 at 7:27

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

• yourreturn does not seem properly indented.
• you should put your test (or basically any code actually doing something) behind amain 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 anassert.
• you can (and should) definebig andsmall as late as possible : we will only need them in theelse case, this is where it belongs.
• the way you loop over the list is not pythonic at all. You should see thefor 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 theelse block or you could get rid of theelse block alltogether as your return in thethen block.

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

import randomdef 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()

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: ...

• python
• algorithm
• recursion
• quick-sort