insertion sorts...

Discussion in 'Python' started by python_newbie, Jun 23, 2008.

  1. 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 < aList[j]:
    aList.insert(j,aList)
    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
     
    python_newbie, Jun 23, 2008
    #1
    1. Advertising

  2. python_newbie

    Terry Reedy Guest

    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 < aList[j]:
    > aList.insert(j,aList)
    > del aList[i+1]


    The last two lines could be replaced with
    aList[j:i+1] = [aList]+aList[j:i]
    which directly replace a slice of the list with a rotated version

    You could also lookup aList just once by adding item = aList
    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
     
    Terry Reedy, Jun 23, 2008
    #2
    1. Advertising

  3. python_newbie

    Matimus Guest

    On Jun 23, 11:52 am, python_newbie <> 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 < aList[j]:
    >                 aList.insert(j,aList)
    >                 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 < aList[j]:`
    the value of `aList` 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
     
    Matimus, Jun 23, 2008
    #3
  4. python_newbie

    Terry Reedy Guest

    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.
     
    Terry Reedy, Jun 24, 2008
    #4
  5. On 24 Haziran, 04:33, Terry Reedy <> 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 ?
     
    python_newbie, Jun 25, 2008
    #5
  6. python_newbie

    MRAB Guest

    On Jun 25, 11:37 am, "A.T.Hofkamp" <> wrote:
    > On 2008-06-25, python_newbie <> wrote:
    >
    > > On 24 Haziran, 04:33, Terry Reedy <> 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
     
    MRAB, Jun 25, 2008
    #6
  7. On 25 Haziran, 17:44, MRAB <> wrote:
    > On Jun 25, 11:37 am, "A.T.Hofkamp" <> wrote:
    >
    >
    >
    > > On 2008-06-25, python_newbie <> wrote:

    >
    > > > On 24 Haziran, 04:33, Terry Reedy <> 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 ?
     
    python_newbie, Jun 30, 2008
    #7
  8. Le Monday 30 June 2008 16:29:11 python_newbie, vous avez écrit :
    > On 25 Haziran, 17:44, MRAB <> wrote:
    > > On Jun 25, 11:37 am, "A.T.Hofkamp" <> wrote:
    > > > On 2008-06-25, python_newbie <> wrote:
    > > > > On 24 Haziran, 04:33, Terry Reedy <> 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
     
    Maric Michaud, Jun 30, 2008
    #8
  9. python_newbie

    MRAB Guest

    On Jun 30, 3:29 pm, python_newbie <> wrote:
    > On 25 Haziran, 17:44, MRAB <> wrote:
    >
    >
    >
    > > On Jun 25, 11:37 am, "A.T.Hofkamp" <> wrote:

    >
    > > > On 2008-06-25, python_newbie <> wrote:

    >
    > > > > On 24 Haziran, 04:33, Terry Reedy <> 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! :))
     
    MRAB, Jun 30, 2008
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Srikanth Mandava
    Replies:
    1
    Views:
    410
    Michael Hudson
    Feb 19, 2004
  2. Replies:
    6
    Views:
    398
  3. Ron Adam

    Alphabetical sorts

    Ron Adam, Oct 16, 2006, in forum: Python
    Replies:
    7
    Views:
    491
    Ron Adam
    Oct 17, 2006
  4. CMOS
    Replies:
    1
    Views:
    342
    Jack Klein
    Aug 29, 2006
  5. Jonathan Wood
    Replies:
    2
    Views:
    343
    Jonathan Wood
    Jun 18, 2008
Loading...

Share This Page