[Tutor] sorting algorithm

[Dave Angel]

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

DaveA