insertion sorts...

[python_newbie]

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

[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

[Matimus]

On Jun 23, 11:52*am, python_newbie <[e-mail]:

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

[Terry Reedy]

Matimus wrote:

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`.

I thought of suggesting that, but indirectly iterating over a list that
is being modified with enumerate has the same problem as directly
interating over the same changing list.

[python_newbie]

On 24 Haziran, 04:33, Terry Reedy <[e-mail]:

Matimus wrote:

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`.

I thought of suggesting that, but indirectly iterating over a list that
is being modified with enumerate has the same problem as directly
interating over the same changing list.

Thanks for all answers. At the end i ve only one point. If a decide to
copy list to iterate when will i have to do this ? Before the
iteration ? And then iterate through one list and change value of the
other ?

[A.T.Hofkamp]

On 2008-06-25, python_newbie <se********@gmail.comwrote:

On 24 Haziran, 04:33, Terry Reedy <[e-mail]:
Thanks for all answers. At the end i ve only one point. If a decide to
copy list to iterate when will i have to do this ? Before the
iteration ? And then iterate through one list and change value of the
other ?

Before starting the iteration would be a good point....

I usually do in such cases:

for x in mylist[:]:
...

making a copy just before the for loop starts.
Lately, I have started avoiding in-place modification of lists. Instead, I
construct a new list from scratch inside the for-loop, and replace the old list
with the newly constructed list afterwards like:

new_list = []
for x in mylist:
....
new_list.append(x)

mylist = new_list

by appending a different value than the original or by not appending, you can
influence the contents of the new list.

I find this solution nicer than in-place modification of an existing list.
Sincerely,
Albert

[MRAB]

On Jun 25, 11:37*am, "A.T.Hofkamp" <[e-mail]:

On 2008-06-25, python_newbie <[e-mail]:

On 24 Haziran, 04:33, Terry Reedy <[e-mail]:
Thanks for all answers. At the end i ve only one point. If a decide to
copy list to iterate when will i have to do this ? Before the
iteration ? And then iterate through one list and change value of the
other ?

Before starting the iteration would be a good point....

I usually do in such cases:

for x in mylist[:]:
* *...

making a copy just before the for loop starts.

Lately, I have started avoiding in-place modification of lists. Instead, I
construct a new list from scratch inside the for-loop, and replace the old list
with the newly constructed list afterwards like:

new_list = []
for x in mylist:
* *....
* *new_list.append(x)

mylist = new_list

by appending a different value than the original or by not appending, youcan
influence the contents of the new list.

I find this solution nicer than in-place modification of an existing list..

Sincerely,
Albert

And if you were originally doing in-place modification because there
were also other references to the list then you could just do:

mylist[:] = new_list

[python_newbie]

On 25 Haziran, 17:44, MRAB <[e-mail]:

On Jun 25, 11:37*am, "A.T.Hofkamp" <[e-mail]:

On 2008-06-25, python_newbie <[e-mail]:

On 24 Haziran, 04:33, Terry Reedy <[e-mail]:
Thanks for all answers. At the end i ve only one point. If a decide to
copy list to iterate when will i have to do this ? Before the
iteration ? And then iterate through one list and change value of the
other ?

Before starting the iteration would be a good point....

I usually do in such cases:

for x in mylist[:]:
* *...

making a copy just before the for loop starts.

Lately, I have started avoiding in-place modification of lists. Instead, I
construct a new list from scratch inside the for-loop, and replace the old list
with the newly constructed list afterwards like:

new_list = []
for x in mylist:
* *....
* *new_list.append(x)

mylist = new_list

by appending a different value than the original or by not appending, you can
influence the contents of the new list.

I find this solution nicer than in-place modification of an existing list.

Sincerely,
Albert

And if you were originally doing in-place modification because there
were also other references to the list then you could just do:

mylist[:] = new_list

Thanks again. I see that you use two different syntax for lists
"mylist = new_list" and "mylist[:] = new_list" these are same i
think ?

[Maric Michaud]

Le Monday 30 June 2008 16:29:11 python_newbie, vous avez écrit*:

On 25 Haziran, 17:44, MRAB <[e-mail]:

On Jun 25, 11:37*am, "A.T.Hofkamp" <[e-mail]:

On 2008-06-25, python_newbie <[e-mail]:
On 24 Haziran, 04:33, Terry Reedy <[e-mail]:
Thanks for all answers. At the end i ve only one point. If a decide
to copy list to iterate when will i have to do this ? Before the
iteration ? And then iterate through one list and change value of the
other ?
>
Before starting the iteration would be a good point....
>
I usually do in such cases:
>
for x in mylist[:]:
* *...
>
making a copy just before the for loop starts.
>
Lately, I have started avoiding in-place modification of lists.
Instead, I construct a new list from scratch inside the for-loop, and
replace the old list with the newly constructed list afterwards like:
>
new_list = []
for x in mylist:
* *....
* *new_list.append(x)
>
mylist = new_list
>
by appending a different value than the original or by not appending,
you can influence the contents of the new list.
>
I find this solution nicer than in-place modification of an existing
list.
>
Sincerely,
Albert

And if you were originally doing in-place modification because there
were also other references to the list then you could just do:

mylist[:] = new_list

Thanks again. I see that you use two different syntax for lists
"mylist = new_list" and "mylist[:] = new_list" these are same i
think ?

Not at all, try to figure out what happen with the following :

>>>[3]: l=[]

>>>[4]: g=[]

>>>[5]: l == g

...[5]: True

>>>[6]: l is g

...[6]: False

>>>[7]: l = [4]

>>>[8]: l is g

...[8]: False

>>>[9]: l == g

...[9]: False

>>>[10]: l = g

>>>[11]: l is g

...[11]: True

>>>[12]: l[:] = [4]

>>>[13]: l == g

...[13]: True

>>>[14]: l is g

...[14]: True

>>>[15]: g

...[15]: [4]

--
_____________

Maric Michaud

[MRAB]

On Jun 30, 3:29Â*pm, python_newbie <[e-mail]:

On 25 Haziran, 17:44, MRAB <[e-mail]:

On Jun 25, 11:37Â*am, "A.T.Hofkamp" <[e-mail]:

On 2008-06-25, python_newbie <[e-mail]:

On 24 Haziran, 04:33, Terry Reedy <[e-mail]:
Thanks for all answers. At the end i ve only one point. If a decideto
copy list to iterate when will i have to do this ? Before the
iteration ? And then iterate through one list and change value of the
other ?

Before starting the iteration would be a good point....

I usually do in such cases:

for x in mylist[:]:
Â* Â*...

making a copy just before the for loop starts.

Lately, I have started avoiding in-place modification of lists. Instead, I
construct a new list from scratch inside the for-loop, and replace the old list
with the newly constructed list afterwards like:

new_list = []
for x in mylist:
Â* Â*....
Â* Â*new_list.append(x)

mylist = new_list

by appending a different value than the original or by not appending,you can
influence the contents of the new list.

I find this solution nicer than in-place modification of an existing list.

Sincerely,
Albert

And if you were originally doing in-place modification because there
were also other references to the list then you could just do:

mylist[:] = new_list

Thanks again. I see that you use two different syntax for lists
"mylist = new_list" and "mylist[:] = new_list" these are same i
think ?

The difference is that "mylist = new_list" makes mylist refer to the
same list as new_list:

Before:

otherlist ───�
├───► [1, 2, 3]
mylist ──────┘

new_list ────────► [4, 5, 6]

After:

otherlist ───────► [1, 2, 3]

mylist ──────�
├───► [4, 5, 6]
new_list ────┘

whereas "mylist[:] = new_list" modifies the list to which mylist
already refers to contain the same items as new_list:

Before:

otherlist ───�
├───► [1, 2, 3]
mylist ──────┘

new_list ────────► [4, 5, 6]

After:

otherlist ───�
├───► [4, 5, 6]
mylist ──────┘

new_list ────────► [4, 5, 6]

(I hope the characters come out OK! :-))