CODEWITHSUNDEEP
pythonsortinginsertion-sort
mv2323
mv2323

Reputation: 47

Logic Impasse in a Simple Insertion Sort

I'm teaching myself Python and I'm having difficulty with a relatively simple concept. The goal is to sort a list in ascending order using insertion sort. Here is the code:

def InsertionSort(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while (i >=0) and (A[i] > key):
            A[i+1] = A[i] # this is the not understood point
            i = i - 1
        A[i+1] = key
    print A

I don't understand how the bolded step works. For example, if I had a list of [6,5,4,3,1] and I got to the second iteration, wouldn't my list now be [6,6,4,3,1]? I'm assigning A[i+1] (in the very first case it would be 5) the value of A[i] (6 in the first case). What happened to my 5? My original attempt at the code was:

def InsertionSort(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while (i >=0) and (A[i] > key):
            temp = A[i+1]
            A [i+1] = A[i]
            A[i] = temp
            i = i - 1
        A[i+1] = key
    print A

This method works too. I don't understand why the first one does as well. Anyone want to take a stab?

Upvotes: 1

Views: 191

Answers (2)

phimuemue
phimuemue

Reputation: 35983

I think it's just because of the line A[i+1]=key.

The first algorithm does the following: Consider the list [1,2,4,5,3], assume we are in iteration where j=4, i.e. we are considering list element 3. The algorighm stores the element 3 in key and checks the following:

[1,2,4,5,3]
       ^    5>3 (key) => move 5 forward by 1 => [1,2,4,5,5]
[1,2,4,5,5]
     ^      4>3 (key) => move 4 forward by 1 => [1,2,4,4,5]
[1,2,4,4,5]
   ^        2<3 => stop inner while loop
now, make A[i+1]=key (remember: key is 3):
[1,2,3,4,5]

In contrast to the above, the second algorithm actually swaps the elements in each iteration:

[1,2,4,5,3]
       ^    5>3 (key) => swap 5 and 3 => [1,2,4,3,5]
[1,2,4,3,5]
     ^      4>3 (key) => swap 4 and 3 => [1,2,3,4,5]
[1,2,3,4,5]
   ^        2<3 => stop while loop 
now, make A[i+1]=key (remember: key is 3): (this is unnecessary!)
[1,2,3,4,5]

Upvotes: 3

Howard
Howard

Reputation: 39197

If you start with [6,5,4,3,1] the iterations will be as follows:

First step:

[6,5,4,3,1] 
    ## first number sorted`

Second step (j=2):

key <- 5

A <- [6,6,4,3,1], i <- -1  
    ## the 5 will be overridden but is still save in the key variable

A <- [5,6,4,3,1]        
    ## A[i+1] = key will restore the 5

The only value which can get "lost" is the one contained in A[j]. But this value is always saved in the variable key and can thus be restored in the very last step.

Upvotes: 2

Related Questions