CODEWITHSUNDEEP
pythonalgorithm
Wizard
Wizard

Reputation: 22083

Problem to implement an insertion algorithms

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?

Upvotes: 0

Views: 39

Answers (1)

Martin Thoma
Martin Thoma

Reputation: 136307

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]

Upvotes: 1

Related Questions