2
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$
# 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.