Re: Quick sort implementation in python
On Sep 25, 11:47 pm, Martin v. Löwis [EMAIL PROTECTED] wrote: 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 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. -- http://mail.python.org/mailman/listinfo/python-list
Quick sort implementation in python
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
On Sep 21, 3:47 am, Steven D'Aprano [EMAIL PROTECTED]
cybersource.com.au wrote:
On Sat, 20 Sep 2008 16:27:41 -0700, Alex Snast wrote:
Another quick question please, is the List data structure just a dynamic
array? If so how can you use static size array, linked list, AVL trees
etcetera.
Before I answer your question, I should say that you can go a LONG way
with just the standard Python built-in data structures list, dict and
set, plus a handful of standard modules like array and collections. It's
often (but not always) better to modify an algorithm to use a built-in
data structure than to try to implement your own.
The underlying data structure for lists is implementation specific. Only
the behaviour is specified by the language.
In the standard Python implementation written in C (usually known as
Python, although sometimes people explicitly describe it as CPython),
lists are implemented as a fixed array of pointers. The array is
periodically resized, either up or down, but only as needed. The largest
consequence of that is that appending to the end of a list is much faster
than inserting at the beginning of the list.
Other implementations (IronPython, Jython, PyPy, CLPython...) are free to
implement lists whatever way they need.
If you want a static list, the simplest way is to create a list and
simply not resize it. If you want to enforce that, here's a subclass to
get you started:
class StaticList(list):
def _resize(self):
raise RuntimeError(list can't be resized)
extend = append = pop = insert = remove = \
__delitem__ = __delslice__ = _resize
I haven't dealt with __setitem__ or __setslice__, because they're more
complicated: you need to make sure the slice you're setting has the same
size as the bit you're replacing, so that this is allowed:
mylist[3:6] = [1, 2, 3]
but not these:
mylist[3:6] = [1, 2]
mylist[3:6] = [1, 2, 3, 4]
As for linked lists and trees, don't worry about pointers, just go ahead
and implement them.
# basic, no-frills tree
class Node(object):
def __init__(self, data, left=None, right=None):
self.left = left
self.right = right
self.info = data
tree = Node('top of the tree')
tree.left = Node('left subtree')
tree.right = Node('right subtree', None, Node('another subtree'))
t = tree.right.right
t.left = Node('yet another subtree')
etc.
The CPython implementation of dict is a hash table, and dicts are
extremely fast and efficient. So long as you don't mind losing the order
of insertion, you won't beat dicts for speed and efficiency in anything
you write in pure Python.
--
Steven
WOW you guys are really helpful, thanks everyone for all the replies.
Last question:
What IDE do you guys recommend, I'm currently using pydev.
Thanks again, Alex
--
http://mail.python.org/mailman/listinfo/python-list
How to make a reverse for loop in python?
Hello I'm new to python and i can't figure out how to write a reverse for loop in python e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
On Sep 20, 8:13 pm, [EMAIL PROTECTED] wrote: Duncan Booth: e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) The exact equivalent would be: for i in range(10, -1, -1): print i I'd use xrange there. Anyway, I have always felt that Python syntax not easy to understand at first sight, expecially when you try to convert a bit more complex inverted for loops from/to C to/from Python. It's one of the few cases where (for example) Pascal (loop) syntax wins a bit over Python syntax :-) Bye, bearophile That's a lot of responses guys. Thanks a lot i think i got it. Another question, are there any pointers in python (or iterators) for when i use a data structure that doesn't support random access? Thanks again, Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: How to make a reverse for loop in python?
On Sep 20, 8:13 pm, [EMAIL PROTECTED] wrote: Duncan Booth: e.g. the python equivalent to the c++ loop for (i = 10; i = 0; --i) The exact equivalent would be: for i in range(10, -1, -1): print i I'd use xrange there. Anyway, I have always felt that Python syntax not easy to understand at first sight, expecially when you try to convert a bit more complex inverted for loops from/to C to/from Python. It's one of the few cases where (for example) Pascal (loop) syntax wins a bit over Python syntax :-) Bye, bearophile Another quick question please, is the List data structure just a dynamic array? If so how can you use static size array, linked list, AVL trees etcetera. -- http://mail.python.org/mailman/listinfo/python-list
