Quick sort implementation in python

[Bruno Desthuilliers]

Alex Snast a écrit :

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

Is that for learning purpose ? Else, it's just a waste of time...

 

[Alex Snast]

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, a[j] = a[j], a
i += 1
a, a[last] = a[last], a
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

 

[bearophileHUGS]

Alex Snast:

However i have no idea how to access the values of a data structure that doesn't allow random access.<

Well, a sorting algorithm can work in-place, sorting the position of
the items inside the given collection, or it can create a new data
structure with the items (in Python all items are references). If the
output of the sorting algorithm is an array (that is a python list),
and the input isn't a list, then you can list-fy your input data and
then sort that list in-place, and return it.

Like this

def mysort(any_iterable):
data = list(any_iterable)
# sort data...
return data

If the input is a list, you can sort it in place.

Finally you may want to return other kinds of collections, like
sorting a linked list and returning it (you can create a chain of
nested lists, and then sort them with a merge sort), but in Python
that's not much common.

Bye,
bearophile

 

[Martin v. Löwis]

Now as you can see I'm passing my list object to both functions along

with their first, last indices

I cannot really see that. More specifically, it isn't definite what the
type of the "a" argument is, nor does the specific type of "a" matter
for the algorithm. It could be a list, or it could be a different
mutable collection that is integer-indexed.

My question is: Is that the normal way to implement algorithms in
python

Yes, it is.

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.

Can you please explain how you did that in C? IOW, how did you do
the partition function (template) in case you don't have random
access to the collection?

Regards,
Martin

 

[Terry Reedy]

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, a[j] = a[j], a
i += 1
a, a[last] = a[last], a
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.

 

[Alex Snast]

I cannot really see that. More specifically, it isn't definite what the
type of the "a" argument is, nor does the specific type of "a" matter
for the algorithm. It could be a list, or it could be a different
mutable collection that is integer-indexed.


Yes, it is.


Can you please explain how you did that in C? IOW, how did you do
the partition function (template) in case you don't have random
access to the collection?

Regards,
Martin

Why exactly do you need random access for partition function? Do can
swap 2 nodes of a linked list without random access (you can swap the
pointers or just swap the node values) and you traverse the list till
you reach it's tail.

 

[sturlamolden]

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

Which is one reason why mergesort i preferred over quicksort for
lists. Pythons built-in sort is a variant of mergesort and should be
fast for linked lists and array lists alike.

 

[Martin v. Löwis]

Can you please explain how you did that in C? IOW, how did you do

Why exactly do you need random access for partition function?

This is a counter-question, not an answer. Let me ask again: How did
you do that in C++?

Do can
swap 2 nodes of a linked list without random access (you can swap the
pointers or just swap the node values) and you traverse the list till
you reach it's tail.

In Python, there is no standard iterator that allows you to modify the
underlying collection. There is the iter() function/type, but it only
allows read access.

Regards,
Martin