Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   insertion sorts... (http://www.velocityreviews.com/forums/t621862-insertion-sorts.html)

 python_newbie 06-23-2008 06:52 PM

insertion sorts...

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 06-23-2008 08:52 PM

Re: insertion sorts...

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 06-23-2008 09:43 PM

Re: insertion sorts...

On Jun 23, 11:52*am, python_newbie <serbule...@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

 Terry Reedy 06-24-2008 01:33 AM

Re: insertion sorts...

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 06-25-2008 09:13 AM

Re: insertion sorts...

On 24 Haziran, 04:33, Terry Reedy <tjre...@udel.edu> wrote:
> 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 ?

 MRAB 06-25-2008 02:44 PM

Re: insertion sorts...

On Jun 25, 11:37*am, "A.T.Hofkamp" <h...@se-162.se.wtb.tue.nl> wrote:
> On 2008-06-25, python_newbie <serbule...@gmail.com> wrote:
>
> > On 24 Haziran, 04:33, Terry Reedy <tjre...@udel.edu> wrote:
> > 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

 python_newbie 06-30-2008 02:29 PM

Re: insertion sorts...

On 25 Haziran, 17:44, MRAB <goo...@mrabarnett.plus.com> wrote:
> On Jun 25, 11:37*am, "A.T.Hofkamp" <h...@se-162.se.wtb.tue.nl> wrote:
>
>
>
> > On 2008-06-25, python_newbie <serbule...@gmail.com> wrote:

>
> > > On 24 Haziran, 04:33, Terry Reedy <tjre...@udel.edu> wrote:
> > > 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 06-30-2008 02:44 PM

Re: insertion sorts...

Le Monday 30 June 2008 16:29:11 python_newbie, vous avez ιcrit*:
> On 25 Haziran, 17:44, MRAB <goo...@mrabarnett.plus.com> wrote:
> > On Jun 25, 11:37*am, "A.T.Hofkamp" <h...@se-162.se.wtb.tue.nl> wrote:
> > > On 2008-06-25, python_newbie <serbule...@gmail.com> wrote:
> > > > On 24 Haziran, 04:33, Terry Reedy <tjre...@udel.edu> wrote:
> > > > 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 06-30-2008 10:35 PM

Re: insertion sorts...

On Jun 30, 3:29Β*pm, python_newbie <serbule...@gmail.com> wrote:
> On 25 Haziran, 17:44, MRAB <goo...@mrabarnett.plus.com> wrote:
>
>
>
> > On Jun 25, 11:37Β*am, "A.T.Hofkamp" <h...@se-162.se.wtb.tue.nl> wrote:

>
> > > On 2008-06-25, python_newbie <serbule...@gmail.com> wrote:

>
> > > > On 24 Haziran, 04:33, Terry Reedy <tjre...@udel.edu> wrote:
> > > > 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 ?

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! :-))

 All times are GMT. The time now is 12:31 PM.