iHere - Lin Cong(丛林)'s Ideas Repository

Quick Sort in python

Tuesday, May. 19. 2009 –  Category: Pythonic  –  0 Comments
Tags: python  sort  algorithm 

def qsort(L):
 if L == []: return []
 return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + qsort([x for x in L[1:] if x>=L[0]])

def qsort(L):
 if len(L) <= 1: return L
 return qsort( [ lt for lt in L[1:] if lt < L[0] ] ) +  
 [ L[0] ] + qsort( [ ge for ge in L[1:] if ge >= L[0] ] )


# IMHO this is almost as nice as the Haskell version from www.haskell.org:
# qsort [] = [] 
# qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
# where 
# elts_lt_x = [y | y <- xs, y < x] 
# elts_greq_x = [y | y <- xs, y >= x]

# And here's a test function:
def qs_test(length):
 import random
 joe = range(length)
 random.shuffle(joe)
 qsJoe = qsort(joe)
 for i in range(len(qsJoe)):
 assert qsJoe[i] == i, 'qsort is broken!'


def qs(ds):
 if len(ds) <= 1: return ds
 pivot = random.choice(ds)
 return qs(filter(lambda x: x < pivot, ds)) +
 [pivot]*ds.count(pivot) +
 qs(filter(lambda x: x > pivot, ds))

q=lambda x:(lambda o=lambda s:[i for i in x if cmp(i,x[0])==s]:len(x)>1 and q(o(-1))+o(0)+q(o(1)) or x)()

def q(x):
 if len(x)>1:
 lt = [i for i in x if cmp(i,x[0]) == -1 ]
 eq = [i for i in x if cmp(i,x[0]) == 0 ]
 gt = [i for i in x if cmp(i,x[0]) == 1 ]
 return q(lt) + q(eq) + q(gt)
 else:
 return x

from random import randrange 
def qsort1a(list):
 """
 Quicksort using list comprehensions and randomized pivot
 >>> qsort1a<>
 <>
 >>> qsort1a<>
 <>
 """
  def qsort(list):
 if list == []: 
 return []
 else:
 pivot = list.pop(randrange(len(list)))
 lesser = qsort([l for l in list if l < pivot])
 greater = qsort([l for l in list if l >= pivot])
 return lesser + [pivot] + greater
 return qsort(list[:])

========================================================================================

App Engine Appengine patch Django Google Google App Engine Google App Engine Java algorithm api app appengine autodiscovery blog cache chat cloud computing cron jobs datastore demo feature fetion fridge gae geo google google app engine google docs googlemaps iHere Blog History ide ihere inforsphere install java jquery map mashup memcache metaweblog new nutch open source pageflow plugin projects pyio python quota release released rss sdk snap sort topStory twitter weblog api 杂记