Quick sort implemented in Python

Question

This code implements quick sort and takes advantage of passing the list by reference. I'm looking for performance and general best practices.

import random
def quicksort(array, l=0, r=-1):
 # array is list to sort, array is going to be passed by reference, this is new to me, try not to suck
 # l is the left bound of the array to be acte on
 # r is the right bound of the array to act on
 if r == -1:
 r = len(array)
 # base case
 if r-l <= 1:
 return
 if r == -1:
 r = len(array)
 piviot = int((r-l)*random.random()) + l
 i = l+1 # Barrier between below and above piviot, first higher element
 swap(array, l, piviot) #piviot is now in index l
 for j in range(l+1,r):
 if array[j] < array[l]:
 swap(array, i, j)
 i = i+1
 swap(array, l, i-1) # i-1 is now the piviot
 quicksort(array, l, i-1)
 quicksort(array, i, r)
 return array
def swap(array, a, b):
 # a and b are the indicies of the array to be swapped
 a2 = array[a]
 array[a] = array[b]
 array[b] = a2
 return

Answer 1

# array is list to sort, array is going to be passed by reference, this is new to me, try not to suck
# l is the left bound of the array to be acte on
# r is the right bound of the array to act on

A comment like that would be better as a docstring.

---

if r == -1:
 r = len(array)

You wrote that twice. The second time is dead code.

---

piviot = int((r-l)*random.random()) + l

The correct spelling is pivot. To generate the random integer, use random.randrange(l, r).

---

def swap(array, a, b):
 # a and b are the indicies of the array to be swapped
 a2 = array[a]
 array[a] = array[b]
 array[b] = a2
 return

The correct spelling is indices.

The return is superfluous. I would omit it.

The swap can be written more simply as array[a], array[b] = array[b], array[a]. That is simple enough that it might be better not to write a swap() function at all.

• Kurt Bourbaki: Actually, using int((r-l)*random.random()) + l is faster than random.randrange(l,r). Could you please explain why you prefer randrange? Is it more reliable? "More random"?
• 200_success: @KurtBourbaki That's interesting. I'm surprised by the huge performance difference. According to the documentation, though, randrange() produces a more uniform distribution than int(random() * n).