def sort(array=[12,4,5,6,7,3,1,15]):
"""Sort the array by using quicksort."""
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
elif x == pivot:
equal.append(x)
elif x > pivot:
greater.append(x)
# Don't forget to return something!
return sort(less)+equal+sort(greater) # Just use the + operator to join lists
# Note that you want equal ^^^^^ not pivot
else: # You need to handle the part at the end of the recursion - when you only have one element in your array, just return the array.
return array
def quicksort(arr):
if len(arr) < 2:
return arr #base case
else:
pivot = arr[0]
less = [i for i in arr[1:] if i <= pivot]
more = [i for i in arr[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(more)
smaller = lambda xs, y: filter(lambda x: x <= y, xs)
larger = lambda xs, y: filter(lambda x: x > y, xs)
qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else []
print qsort([3,1,4,2,5]) == [1,2,3,4,5]
def qsort(arr):
if len(arr) <= 1:
return arr
else:
return qsort([x for x in arr[1:] if x < arr[0]])
+ [arr[0]]
+ qsort([x for x in arr[1:] if x >= arr[0]])
