[Tutor] sorting algorithm
davea at ieee.org
Sat Mar 13 03:11:46 CET 2010
C.T. Matsumoto wrote:
> I've change the code and I think I have what you were talking about.
> def mysort(list_):
> for i in xrange(0, len(list_)):
> pos = i
> for j in xrange(pos+1, len(list_)):
> if list_[i] > list_[j]:
> pos = j
> list_[i], list_[j] = list_[j], list_[i]
> I finally started to think that the while couldn't remain. But if I
> look at this the thing that I don't get is the 'xrange(pos+1,
> len(list_))' snippet. What confused me was how did a new position get
> passed xrange(), when I do not see where it that was happening. Is
> 'pos' a reference to the original pos in the xrange snippet?
That loop is not what I was describing, but I think it's nearly
equivalent in performance. My loop was always swapping adjacent items,
and it adjusted the ending limit as the data gets closer to sorted.
This one adjusts the beginning value (pos) of the inner loop, as the
data gets more sorted. For some orderings, such as if the data is
already fully sorted, my approach would be much faster.
Your outer loop basically finds the smallest item in the list on each
pass. If the line pos=j didn't exist, the inner loop would always loop
from the i+1 value to the end of the list. But since we've already done
a bunch of comparisons on the previous pass, no items before pos need be
compared in the current pass.
I'm going to be quite busy for the next couple of days. So if I don't
respond to your next post quickly, please be patient.
More information about the Tutor