Problem to implement an insertion algorithms

Question

I write such a insertion algorithms:

In [33]: %paste                                                                                                  
def insertion_sort2(arr):
    for i in range(1, len(arr)):
        insert_item = arr[i]
        for j in range(i):#insert to sorted array arr[:i]
            if insert_item < arr[j]:
                arr[j] = insert_item

Test it

In [35]: arr                                                                                                     
Out[35]: [0, 0, 0, 2, 3, 3, 6, 6, 6]
In [36]: arr = list(range(9))                                                                                    
In [37]: random.shuffle(arr)                                                                                     
In [38]: insertion_sort2(arr)                                                                                    
In [39]: arr                                                                                                     
Out[39]: [0, 0, 0, 0, 0, 0, 3, 3, 3]

I check the logic but cannot find any problem.

1. i in arr[1:len]
2. insert arr[i] to arr[:i]

What' the problem with my implementation?

Martin Thoma · Accepted Answer · 2018-11-24 06:10:02Z

1

The line

arr[j] = insert_item

overwrites arr[j]. It does NOT insert.

>>> l = list(range(10))
>>> l
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> l[3] = 'foo'
>>> l
[0, 1, 2, 'foo', 4, 5, 6, 7, 8, 9]
>>> l.insert(7, 'bar')
>>> l
[0, 1, 2, 'foo', 4, 5, 6, 'bar', 7, 8, 9]

answered Nov 24, 2018 at 6:10

Martin Thoma

139k174 gold badges687 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Problem to implement an insertion algorithms

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related