What is wrong with this approach for insertion sort?

Question

Could anyone explain to me why the following method for insertion sort is wrong please?

def insertion_sort(m):
        n = 1
        while n < len(m)-1:
            current_value = m[n]
            if m[n] < m[n-1]:
                m[n] = m[n-1]
                m[n-1] = current_value
            n = n + 1
        return m

#how my code turned out:
m = [7,4,5] returned [4,7,5] instead of [4,5,7]

Nir Alfasi · Answer 1 · 2017-03-24T02:40:55.393

2

See explanations in the code comments:

def insertion_sort(m):
    n = 1
    while n < len(m): # <-- end at the end of the list
        current_value = m[n]
        if m[n] < m[n-1]:
            m[n] = m[n-1]
            m[n-1] = current_value
        n = n + 1
    return m

edited Mar 24 '17 at 02:40

answered Mar 24 '17 at 02:35

Nir Alfasi

53,191
11
86
129

Starting from `1` is fine... no? – juanpa.arrivillaga Mar 24 '17 at 02:37

score 0 · Answer 2 · edited May 23 '17 at 11:46

0

As alfasin mentioned, the problem is with the while loop condition!

You can actually use for loop for this scenario. Take a look at this

And to be more pythonic, you can swap two numbers as a,b = b,a as mentioned in the comments by @TigerhawkT3!

def insertion_sort(m):
    for n in range(len(m)): #iterate from 0 to m-1. auto increment value is by default 1
            if m[n] < m[n-1]: m[n], m[n-1] = m[n-1], m[n]
    return m

print insertion_sort([7,4,5]) return m print insertion_sort([7,4,5])

Output:

[4, 5, 7]

Moreover, the one you've tried isnt actually the insertion sort algorithm. You got to fine tune yours to for list with more than 3 elements!

edited May 23 '17 at 11:46

Community

1
1

answered Mar 24 '17 at 02:39

Keerthana Prabhakaran

3,766
1
13
23

1

If you're going to make it more Pythonic with `range`, you might as well also do a multiple assignment with `if m[n] < m[n-1]: m[n], m[n-1] = m[n-1], m[n]`, and then you don't need `current_value`. – TigerhawkT3 Mar 24 '17 at 02:42
Thanks for the comment. I was about to do that! Anyways I've them in the edit. :) – Keerthana Prabhakaran Mar 24 '17 at 02:50
And, of course, it could be good to note that this only makes one pass, so lists with more than three elements may not be fully sorted. – TigerhawkT3 Mar 24 '17 at 02:58

score 0 · Answer 3 · answered Mar 24 '17 at 04:20

Explanation in the comments

def insertion_sort(array):
    # For each number in the list (not starting 
    # with the first element because the first
    # element has no prior (i.e., no array[j-1])
    for i in range(1, len(array)):
        # Set a temp variable j (totally not necessary
        # but is helpful for the sake of a visual)
        j = i
        # While j is greater than 0 (position 0 is the 
        # very beginning of the array) AND the current 
        # element array[j] is less than the prior element
        # array[j-1] 
        while j>0 and array[j] < array[j-1]:
            # Set the current element equal to the prior 
            # element, and set the prior element equal to
            # the current element (i.e., switch their positions)
            array[j], array[j-1] = array[j-1], array[j]
            # Decrement j (because we are moving each element
            # towards the beginning of the list until it is 
            # in a sorted position)
            j-=1
    return array

 array = [1, 5, 8, 3, 9, 2]

First for-loop iteration: [1,5,8,3,9,2] (5 is already in a sorted position)
Second for-loop iteration: [1,5,8,3,9,2] (8 is already in a sorted position)
Third: [1,3,5,8,9,2] (move 3 back until it's sorted)
Fourth: [1,2,3,8,9] (move 2 back until it's sorted)

Hope this slight illustration helps.

What is wrong with this approach for insertion sort?

3 Answers3