Quick sort implementation in python

Alex Snast asnast at gmail.com
Thu Sep 25 21:33:07 CEST 2008

Hi guys, I've been learning python in the past week and tried to
implement a q.sort algorithm in python as follows:

def quick_sort(l, first, last)
    if first < last:
        q = partition(a, first, last)
        quick_sort(a, first, q - 1)
        quick_sort(a, q + 1, last)

def partition(a, first, last):
    import random
    pivot = random.randomint(first, last)
    a[last], a[pivot] = a[pivot], a[last]

    i = first
    for j in range(first, last):
        if a[j] <= a[last]:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[last] = a[last], a[i]
    return i

Now as you can see I'm passing my list object to both functions along
with their first, last indices

My question is: Is that the normal way to implement algorithms in
python cause in c++ i've implemented that algo via a template function
which can have a randon access data structure or not. However i have
no idea how to access the values of a data structure that doesn't
allow random access.

Thanks, Alex

More information about the Python-list mailing list