Skip to content

Instantly share code, notes, and snippets.

@dpapathanasiou
Created March 25, 2019 01:02
Show Gist options
  • Save dpapathanasiou/0e5f49173c1194d3769d630a19ae6f06 to your computer and use it in GitHub Desktop.
Save dpapathanasiou/0e5f49173c1194d3769d630a19ae6f06 to your computer and use it in GitHub Desktop.
Quicksort in Python
#!/usr/bin/env python
"""
An implementation in python, inspired by the version in "Learn You
a Haskell for Great Good!"
(http://learnyouahaskell.com/recursion#quick-sort)
"""
def quicksort (a):
if len(a) < 2:
return a
else:
p = a[0]
l = quicksort(filter(lambda x: x <= p, a[1:]))
r = quicksort(filter(lambda x: x > p, a[1:]))
return l + [p] + r
"""
Test it, using the example arrays from the text:
1 - a numeric array
2 - a string (array of chars)
"""
narr = [10,2,5,3,1,6,7,4,2,3,4,8,9]
nexp = [1,2,2,3,3,4,4,5,6,7,8,9,10]
nres = quicksort(narr)
print 'sorting', narr, '->', nres
assert nres == nexp, 'expected ' + nexp + ' from sorting ' + narr + ' but got ' + nres
# using list() to keep the type system happy
sarr = list("the quick brown fox jumps over the lazy dog")
sexp = list(" abcdeeefghhijklmnoooopqrrsttuuvwxyz")
sres = quicksort(sarr)
print 'sorting "' + ''.join(sarr) + '" -> "' + ''.join(sres) + '"'
assert sres == sexp, 'expected "' + ''.join(sexp) + '" from sorting "' + ''.join(sarr) + '" but got "' + ''.join(sres) + '"'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment