Home Original page

Quick sort implementation in python

Terry Reedy tjreedy at udel.edu
Fri Sep 26 02:43:44 EDT 2008 
Alex Snast wrote:
> 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)

You changed the name of the list to be sorted from 'l' to 'a'.
Please post code that works by cut-and-paste.

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

That depends on the data structure.  Access to a singly-linked list is 
by linear scanning from the front.
More information about the Python-list mailing list