Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > insertion sorts...

Reply
Thread Tools

insertion sorts...

 
 
python_newbie
Guest
Posts: n/a
 
      06-23-2008
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
 
Reply With Quote
 
 
 
 
Terry Reedy
Guest
Posts: n/a
 
      06-23-2008


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



 
Reply With Quote
 
 
 
 
Matimus
Guest
Posts: n/a
 
      06-23-2008
On Jun 23, 11:52*am, python_newbie <(E-Mail Removed)> 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
 
Reply With Quote
 
Terry Reedy
Guest
Posts: n/a
 
      06-24-2008


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.

 
Reply With Quote
 
python_newbie
Guest
Posts: n/a
 
      06-25-2008
On 24 Haziran, 04:33, Terry Reedy <(E-Mail Removed)> 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 ?
 
Reply With Quote
 
MRAB
Guest
Posts: n/a
 
      06-25-2008
On Jun 25, 11:37*am, "A.T.Hofkamp" <(E-Mail Removed)> wrote:
> On 2008-06-25, python_newbie <(E-Mail Removed)> wrote:
>
> > On 24 Haziran, 04:33, Terry Reedy <(E-Mail Removed)> 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
 
Reply With Quote
 
python_newbie
Guest
Posts: n/a
 
      06-30-2008
On 25 Haziran, 17:44, MRAB <(E-Mail Removed)> wrote:
> On Jun 25, 11:37*am, "A.T.Hofkamp" <(E-Mail Removed)> wrote:
>
>
>
> > On 2008-06-25, python_newbie <(E-Mail Removed)> wrote:

>
> > > On 24 Haziran, 04:33, Terry Reedy <(E-Mail Removed)> 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 ?
 
Reply With Quote
 
Maric Michaud
Guest
Posts: n/a
 
      06-30-2008
Le Monday 30 June 2008 16:29:11 python_newbie, vous avez ιcrit*:
> On 25 Haziran, 17:44, MRAB <(E-Mail Removed)> wrote:
> > On Jun 25, 11:37*am, "A.T.Hofkamp" <(E-Mail Removed)> wrote:
> > > On 2008-06-25, python_newbie <(E-Mail Removed)> wrote:
> > > > On 24 Haziran, 04:33, Terry Reedy <(E-Mail Removed)> 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

 
Reply With Quote
 
MRAB
Guest
Posts: n/a
 
      06-30-2008
On Jun 30, 3:29Β*pm, python_newbie <(E-Mail Removed)> wrote:
> On 25 Haziran, 17:44, MRAB <(E-Mail Removed)> wrote:
>
>
>
> > On Jun 25, 11:37Β*am, "A.T.Hofkamp" <(E-Mail Removed)> wrote:

>
> > > On 2008-06-25, python_newbie <(E-Mail Removed)> wrote:

>
> > > > On 24 Haziran, 04:33, Terry Reedy <(E-Mail Removed)> 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! )
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
ACLs insertion and management on 837. AM Cisco 2 01-08-2005 02:20 PM
ACLs insertion and management on 837. AM Cisco 0 01-08-2005 02:07 PM
Online Insertion and Removal 7206VXR Fischer Karsten Cisco 6 12-03-2004 10:56 PM
Insertion delay rajan VHDL 1 09-18-2004 08:11 PM
automatic insertion of controls on codebehind Boban Dragojlovic ASP .Net 4 07-24-2003 03:36 PM



Advertisments