473,841 Members | 1,782 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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.ind ex(iterator)):
if iterator < number:
aList.insert(aL ist.index(numbe r),iterator)
del aList[aList.index(ite rator)+1]

if __name__ == "__main__":

MyList = [7,3,5,19,8,2,9, 4,15,6,8,3,19]
insertion_sort( MyList)
print MyList
Jun 27 '08 #1
9 2066


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.ind ex(iterator)):
if iterator < number:
aList.insert(aL ist.index(numbe r),iterator)
del aList[aList.index(ite rator)+1]
Calculating alist.index(ite m) 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(aL ist.index(numbe r),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(ite m)
for number in range(i):
if item < aList[number]:
aList.insert(nu mber,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

Jun 27 '08 #2
On Jun 23, 11:52*am, python_newbie <serbule...@gma il.comwrote:
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.ind ex(iterator)):
* * * * * * if iterator < number:
* * * * * * * * aList.insert(aL ist.index(numbe r),iterator)
* * * * * * * * del aList[aList.index(ite rator)+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
Jun 27 '08 #3


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.

Jun 27 '08 #4
On 24 Haziran, 04:33, Terry Reedy <tjre...@udel.e duwrote:
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 ?
Jun 27 '08 #5
On 2008-06-25, python_newbie <se********@gma il.comwrote:
On 24 Haziran, 04:33, Terry Reedy <tjre...@udel.e duwrote:
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
Jun 27 '08 #6
On Jun 25, 11:37*am, "A.T.Hofkam p" <h...@se-162.se.wtb.tue. nlwrote:
On 2008-06-25, python_newbie <serbule...@gma il.comwrote:
On 24 Haziran, 04:33, Terry Reedy <tjre...@udel.e duwrote:
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.appen d(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
Jun 27 '08 #7
On 25 Haziran, 17:44, MRAB <goo...@mrabarn ett.plus.comwro te:
On Jun 25, 11:37*am, "A.T.Hofkam p" <h...@se-162.se.wtb.tue. nlwrote:
On 2008-06-25, python_newbie <serbule...@gma il.comwrote:
On 24 Haziran, 04:33, Terry Reedy <tjre...@udel.e duwrote:
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.appen d(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 ?
Jun 30 '08 #8
Le Monday 30 June 2008 16:29:11 python_newbie, vous avez ιcrit*:
On 25 Haziran, 17:44, MRAB <goo...@mrabarn ett.plus.comwro te:
On Jun 25, 11:37*am, "A.T.Hofkam p" <h...@se-162.se.wtb.tue. nlwrote:
On 2008-06-25, python_newbie <serbule...@gma il.comwrote:
On 24 Haziran, 04:33, Terry Reedy <tjre...@udel.e duwrote:
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.appen d(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

Jun 30 '08 #9
On Jun 30, 3:29Β*pm, python_newbie <serbule...@gma il.comwrote:
On 25 Haziran, 17:44, MRAB <goo...@mrabarn ett.plus.comwro te:
On Jun 25, 11:37Β*am, "A.T.Hofkam p" <h...@se-162.se.wtb.tue. nlwrote:
On 2008-06-25, python_newbie <serbule...@gma il.comwrote:
On 24 Haziran, 04:33, Terry Reedy <tjre...@udel.e duwrote:
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.appe nd(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! :-))
Jun 30 '08 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
2151
by: Jason | last post by:
Looking for some insight from the professionals about how they handle row inserts. Specifically single row inserts through a stored procedure versus bulk inserts. One argument are people who say all inserts (and updates and deletions I guess) should go through stored procedures. The reasoning is that the developers that code the client side have no reason to understand HOW the data is stored, just that it is. Another problem is an insert...
20
3878
by: Patrick Guio | last post by:
Dear all, I have some problem with insertion operator together with namespace. I have a header file foo.h containing declaration of classes, typedefs and insertion operators for the typedefs in a named namespace namespace foo { class Foo
10
2745
by: Anton.Nikiforov | last post by:
Dear all, i have a problem with insertion data and running post insert trigger on it. Preambula: there is a table named raw: ipsrc | cidr ipdst | cidr bytes | bigint time | timestamp Triggers:
5
6069
by: John N. | last post by:
Hi All, Here I have a linked list each containing a char and is double linked. Then I have a pointer to an item in that list which is the current insertion point. In this funtion, the user hits the right and left keys to move this insertion point (cursor) Here is the problem:
4
1591
by: Andrix | last post by:
Hi, I have a table with 20.000.000 of tuples. I have been monitoring the performance of the insertion and updates, but not convince me at all. The table have 30 columns, what and 12 of it, are calcultated column. The test that i do was this: 1 Insertion with all the columns and calculing the calcultated columns in the insertion sentence.
0
3854
by: polocar | last post by:
Hi, I have noticed a strange behaviour of CurrencyManager objects in C# (I use Visual Studio 2005 Professional Edition). Suppose that you have a SQL Server database with 2 tables called "Cities" and "Persons", and that: "Cities" has 2 fields called "IDCity" and "NameCity" "Persons" has 3 fields called "IDPerson", "NamePerson" and "IDCityAddress" with "IDCity" and "IDCityAddress" fields relationed with the classical father-child relation...
28
3460
by: Peter Michaux | last post by:
Hi, I'm playing with dynamic script insertion to make a request to the server for a JavaScript file to be automatically run when it arrives in the browser. It works but... The page caching is too good. When I revisit the page or refresh the page, and then redo the script insertion, the browser doesn't even hit the server to check for a newer version of the JavaScript file. The same old script runs with each insertion.
6
2328
by: barcaroller | last post by:
If I insert/remove an element in a set, will an iterator to this set automatically become invalid? Does the position of the iterator before the insertion/removal matter? How are vectors and lists affected?
3
4696
by: kvnsmnsn | last post by:
I've been asked to overload the insertion operator. What exactly is the insertion operator in C++, and how would one overload it? I think that in C I could overload the "+" operator like so: double operator+ ( char* left , char* right) { // some code here }
0
9865
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9709
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
1
10668
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9446
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
7025
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5882
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4498
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4085
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3140
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.