Improving quick sort algorithm (Python)

Question

I'm learning algorithm and this is my implementation of quick sort, please guide how can i improve it further and what are other more optimal ways to implement quick sort?

def quick_sort(arr):
 length = len(arr)
 if length <= 1:
 return arr
 else:
 pivot = arr.pop()
 items_greater = []
 items_lower = []
 for item in arr:
 if item > pivot:
 items_greater.append(item)
 else:
 items_lower.append(item)
 return quick_sort(items_lower)+[pivot]+quick_sort(items_greater)

• πάντα ῥεῖ: Are you sure that your indentation is correct?

Answer 1

Unnecessary else:

 if length <= 1:
 return arr
 else:
 pivot = arr.pop()
 ...

If the first path is taken, the method exits. If the second path is taken, then execution continues with the remainder of the method. So you could write the rest of the method inside the else: clause:

 if length <= 1:
 return arr
 else:
 pivot = arr.pop()
 ... # Now part of the else statement

Or, for more "left leaning" code, remove the else: clause altogether:

 if length <= 1:
 return arr
 pivot = arr.pop()
 ...

Loop like a native

 items_greater = []
 items_lower = []
 for item in arr:
 if item > pivot:
 items_greater.append(item)
 else:
 items_lower.append(item)

Here, you are creating a list, and then calling .append() to repeatedly add items to that list in a loop. Python has a builtin mechanism to do this, faster. List comprehension:

 items_greater = [item for item in arr if item > pivot]
 items_lower = [item for item in arr if not(item > pivot)]

Why not(item > pivot), and not simply item <= pivot? For the most part, the latter will work. But there are gotchas and special cases. If there are infinities (+Inf, -Inf) or a not-a-numbers (NaN) in the list, items might be omitted from both lists. For example, if the list contains a NaN, both NaN > 10 and NaN <= 10 are False, which would result in that item not being added to either the items_greater or the items_lower lists! Worse, if pivot happened to become NaN, then all arr items would be excluded! Similarly, if there are two infinities in the list, both +Inf > +Inf and +Inf <= +Inf are False.

PEP-8

The PEP-8 coding standard has many suggestion about how to format code. Binary operators, for example, should have a single space on either side of the binary operator.

 return quick_sort(items_lower)+[pivot]+quick_sort(items_greater)

should be:

 return quick_sort(items_lower) + [pivot] + quick_sort(items_greater)

• Steven Fontanella: Would you expect the list comprehension to go faster? It's doing two passes instead of one.

Answer 2

Document your code. In the code: while
quick_sort(arr) is telling to an extent (sort into (ascending "natural") order (between pairs of arr's elements), additional space no worse than proportional to input size, processing time no worse than proportional to its square),
arr isn't: what, in Python, is an array? The way arr is used, any sequence would do nicely -
for lack of a useful docstring, I'd have to inspect the code to find out.
And does quick_sort(arr) keep the relative order of equal items?
Does it return something useful? What, exactly?
Does it sort in place? (Modify arr (if not ordered) (most implementations of quicksort do), use additional space negligible compared to arr's size)

• Keep promises, explicit or implied
  For all I can see, your code uses additional space proportional to the square of length, worst case: not tolerable for a "production" implementation

While it is feasible to prevent disadvantageous splits via pivot choice, it is much simpler to reduce ill effects on space requirements using recursion for the non-larger partition, only, and iterating on the non-smaller one.