# Quick sort implemented in Python

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


# 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.

• 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"? – Kurt Bourbaki Dec 12 '16 at 21:45
• @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). – 200_success Dec 13 '16 at 0:06