Quick Sort In Python

This is an implementation of QuickSort in the PythonLanguage. (Not the most efficient solution to the problem, because it creates sublists in each iteration.)

It chooses a random Element as PivotElement? to avoid the WorstCase? for QuickSort.

 import random
 def quicksort(L):
   if len(L) > 1:
     pivot = random.randrange(len(L))
     elements = L[:pivot]+L[pivot+1:]
     left  = [element for element in elements if element < L[pivot]] 
     right =[element for element in elements if element >= L[pivot]]
     return quicksort(left)+[L[pivot]]+quicksort(right)
   return L

---

The above has exceptionally bad performance if the list is constant. Here is an alternative:

  import random
  def qsort(L):
    if len(L)<2: return L
    pivot_element = random.choice(L)
    small = [i for i in L if i< pivot_element]
    medium = [i for i in L if i==pivot_element]
    large = [i for i in L if i> pivot_element]
    return qsort(small) + medium + qsort(large)

You can inline the small, medium and large if you like.

---

Sometimes you're not sorting something as simple as integers, sometimes you're sorting things that are horrendously complex to compare. In that case you don't want to run down your list three times comparing against the pivot element lots of times. Suppose you have a super-optimised function compare that gives you back -1, 0 or 1 in the usual fashion. Here's another way to conceptualise the sorting:

  import random

  # Example in case you want to compare simple things.
  #  def compare(a,b):
  #      if a<b: return -1
  #      if a>b: return 1
  #      return 0

  def distribute(bins,L,fn):
      for item in L:
          bins[fn(item)].append(item)

  def qsort(L):
    if len(L)<2: return L
    pivot_element = random.choice(L)
    bins = {-1:[],0:[],1:[]}
    distribute(bins,L, lambda x: compare(x,pivot_element) )
    return qsort(bins[-1])+bins[0]+qsort(bins[1])

You can avoid the lambda by passing in the pivot_element and compare function to distribute, etc. There are other improvements, but the idea's the important thing.

---

In terms of functional programming

  qs = lambda xs : qs( [x for x in xs[1:] if x <  xs[0]] ) +
                       [xs[0]]                             +
                   qs( [x for x in xs[1:] if x >= xs[0]] )
                   if len(xs) > 1 else xs

The strafe forward alternative with "x and y or z" will not work because y can be zero or empty as described in "4.16. Is there an equivalent of C's "?:" ternary operator?" on

  http://mail.python.org/pipermail/python-announce-list/1999-July/000105.html

  qs = lambda xs : (len(xs) <=1 and xs) or
                   ( qs( [x for x in xs[1:] if x <  xs[0]] ) +
                         [xs[0]]                             +
                     qs( [x for x in xs[1:] if x >= xs[0]] ) )

It ends up in "RuntimeError?: maximum recursion depth exceeded".

However, the "hacky" version of it works fine

  qs = lambda xs : ( (len(xs) <= 1 and [xs]) or
                     [ qs( [x for x in xs[1:] if x < xs[0]] ) +
                           [xs[0]]                            +
                       qs( [x for x in xs[1:] if x >= xs[0]] ) ] )[0]

Python 2.7.2 (32 bit).

---

CategoryPython