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