insertion sorts...

[Matimus]

On Jun 23, 11:52 am, python_newbie <serbule... at gmail.com> wrote:
> I don't know this list is the right place for newbie questions. I try
> to implement insertion sort in pyhton. At first code there is no
> problem. But the second one ( i code it in the same pattern i think )
> doesn't work. Any ideas ?
>
> ------------------------------------------------------------
> 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]
>
> 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:
>         for number in range(aList.index(iterator)):
>             if iterator < number:
>                 aList.insert(aList.index(number),iterator)
>                 del aList[aList.index(iterator)+1]
>
> if __name__ == "__main__":
>
>     MyList = [7,3,5,19,8,2,9,4,15,6,8,3,19]
>     insertion_sort(MyList)
>     print MyList

In your second attempt `number` is still essentially the same thing as
`j` was in the first one. In the following line however, you treat
`number` as if it is the actual value. It _should_ be `if iterator <
aList[number]`.

Also, you are missing a `break` after you do an insertion (this goes
for both versions). The bigger question is why did the first one work?
I think it works because in this statement `if aList[i] < aList[j]:`
the value of `aList[i]` changes after the insertion to a different
value. Because of the way this algorithm works, that _new_ value is
guaranteed to be >= `aList[j]` so the insertion is never performed
again. In the second version `iterator` stays as the original value
even after it makes an insertion. This will cause it to perform the
insertion multiple times.

May I suggest you look into using `enumerate`:

>>> for i, val in enumerate([4,5,6]):
...  print i, val
...
0 4
1 5
2 6

It allows you to get the index and the value at the same time, which
should eliminate the need for `aList.index`.

Matt