insertion sorts...

[Terry Reedy]

python_newbie wrote:
> I don't know this list is the right place for newbie questions.

It is.  We get them all the time.  There is also a tutor mailing list.

 > I try to implement insertion sort in pyhton.

python

 > At first code there is no problem.

It is pretty straightforward.

>But the second one ( i code it in the same pattern i think )

Same pattern, but different algorithm as written.

> doesn't work. Any ideas ?

When something 'doesn't work', you should post how and some details.  If 
an exception is raised, *cut and paste* the full traceback and error 
message after examining it yourself.  If bad output is produced, *cut 
and paste* that.  Here is it obvious what good output would be.  When it 
is not, say what you expected that is different.

In this case, I am not sure why you think the new algorithm will work.
But I suspect you were not trying to write a different algorithm ;-)
see below.

> ------------------------------------------------------------
> def insertion_sort(aList):
> 
>     for i in range(len(aList)):
>         for j in range(i):
>             if aList[i] < aList[j]:
>                 aList.insert(j,aList[i])
>                 del aList[i+1]

The last two lines could be replaced with
             aList[j:i+1] = [aList[i]]+aList[j:i]
which directly replace a slice of the list with a rotated version

You could also lookup aList[i] just once by adding item = aList[i] 
before the j loop.  This also makes the code slightly easier to read.

> if __name__ == "__main__":
> 
>     MyList = [7,3,5,19,8,2,9,4,15,6,8,3,19]
>     insertion_sort(MyList)
>     print MyList
> -------------------------------------------------------------
> 
> def insertion_sort(aList):
> 
>     for iterator in aList:

The members of aList are 'items' or whatever, but not iterators.

>         for number in range(aList.index(iterator)):
>             if iterator < number:
>                 aList.insert(aList.index(number),iterator)
>                 del aList[aList.index(iterator)+1]

Calculating alist.index(item) twice is bad.  Do it once before the inner 
loop.


> if __name__ == "__main__":
> 
>     MyList = [7,3,5,19,8,2,9,4,15,6,8,3,19]
>     insertion_sort(MyList)
>     print MyList

Here is the error message you omitted

Traceback (most recent call last):
   File "C:\Program Files\Python30\misc\temp", line 12, in <module>
     insertion_sort(MyList)
   File "C:\Program Files\Python30\misc\temp", line 6, in insertion_sort
     aList.insert(aList.index(number),iterator)
ValueError: list.index(x): x not in list

I believe you meant to insert at number, which is a position, not 
index(position), which only accidentally works.  With that corrected, I 
believe you were trying to write

     for item in aList:
         i = aList.index(item)
         for number in range(i):
             if item < aList[number]:
                 aList.insert(number,item)
                 del aList[i+1]

which looks parallel to the first code, which runs, but which does not 
sort.  The difference is iterating through items instead of positions.

The problem is that aList is being modified inside the loop.  That 
usually is a bad idea.  If you want to sort the list in place without 
either copying the list or building a new sorted list, you have to use 
indexes.

Terry Jan Reedy