Quicksort implementation using filter() to perform partitioning

from operator import ge as greater, lt as lesser

def qsort(L):
if len(L) <= 1: return L
pivot   = L
sublist = lambda op: [*filter(lambda num: op(num, pivot), L[1:])]

return qsort(sublist(lesser))+ [pivot] + qsort(sublist(greater))

It seems like an overkill to have two lambdas in the sublist definition. How can I refactor the sublist lambda function to not include lambda at all?

• Are you aware that quicksort is conventionally done in-place, for efficiency? Jun 22 '17 at 20:30

I think having one lambda in your definition of sublist is perfectly appropriate, but the use of filter isn't appropriate because you are going to need a list anyway. You aren't using it wrong, there are just better solutions.

Also, as noted in the other answer, you can avoid repeated slicing L by creating a copy of the list on the first run of the function through an optional default argument (see first in the code below).

Finally, summing three lists in your return statement is probably less than optimal. With unpacking in Python 3, you can turn this into a single comprehension which should be better in terms of intermediate object creation.

from operator import ge, lt

def qsort(L, first=True):
if len(L) <= 1:
return L

L = L[:] if first else L
pivot = L.pop()
sublist = lambda op: [n for n in L if op(n, pivot)]

return [*qsort(sublist(lt), False), pivot, *qsort(sublist(ge), False)]
• Somewhere in my surfs, there was a mention of a generator function as being relevant to this task. Any thoughts? Jun 22 '17 at 18:34

Eliminating "the other lambda" for comparison:

from operator import ge as greaterEqual, lt as lesser

def sublist(L, op, pivot):
""" return a list of items num from L satisfying op(num, pivot) """
return [*filter(lambda num: op(num, pivot), L)]

def qsort(L):
""" return a partition-sorted list of the L's items """
if len(L) <= 1: return L
pivot   = L
t = L[1:]
return qsort(sublist(t, lesser, pivot)
) + [pivot
] + qsort(sublist(t, greaterEqual, pivot))

("Everything" about comprehension vs. filter and about in-place and slicing has been said.)

No. If you want to make a filter object a list, use list. Also it'd be clearer if you used a list comprehension instead.

sublist = lambda op: [num for num in L[1:] if op(num, pivot)]

Also, this isn't very efficient, the list comprehension is making a list, and so is l[1:]. It'd be better in terms of memory if you instead performed all operations on one list. If you don't want to do that, using pivot = L.pop() would allow you to half the amount of list you're making, as then you can use L rather than L[1:].

• L.pop() would mutate to my incoming list. Is that a good practice? Since some form of filtering is happening, just for academic purposes, how would I weave in a filter in combination with a operator in the code? Jun 22 '17 at 15:32