help understanding code

[leegeorg07]

hi again i have been learning about algorithm solving and designing from the website here

i sort of understood the first code but before i went on any further i wanted to understand it the code is

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]
            i = i - 1
        A[i+1] = key

x = [65,88,2,9876,33,8]

InsertionSort(x)

print x

any help understanding it would be welcomed thanks

[lllllIllIlllI]

This is a sorting function.
It grabs a number from the list, that is now the key.
Then in the while loop it moves the values to the right if they are more then the key, so essentially, it gets a number from a list. It then compares it with the other numbers and if the number they compare it with is bigger the bigger number moves to the end of the list.
Do you need a more detailed explaination?

[leegeorg07]

yes please that would be helpful
i essentially want to know what each bit of code does if you can help me with this then i would be very grateful

[lllllIllIlllI]

Okay, here goes:

The program starts off and we have our list called A. This has in it, 65,88,2,9876,33,8. Okay.
the program then uses a range to iterate over. To start off with the program makes J the value of 1.
The key will then equal 88 because thats whats at A[1]. But now i will equal 0. Because of that the loop will not go through and i+1 = key, for this iteration this does nothing because 0+1 = 1 so A[1] = A[1].

Now the next iteration of the range has J as 2. Sorry im going through this slowly, but this is what i find is useful for a full understanding. So the key will equal 2. the vairable i will now equal 1 and the loop will go through because i is more than 0 (or equal to). And also 88 (a) is more than 2. So as we go through the loop we start by moving things. The first thing we move is A[i+1] i+1 = 2 so we are moving our number 2. We replace number 2 with 88 and then subtract 1 from i and keep going. Now i is 0 and the list look like this: 65,88,88,9876,33,8.
This time the program asks, is A > key, A = 65 so thats true and also i is not less than one. This time the loop goes through through things move again, A[i+1] (88) = A (65) so now the loop will look like this 65,65,88,9876,33,8. And i is decremented. But the loop does not run again because i is not more than or equal to 0. So the last statement is run, A[i+1] = key. i equals -1 so this is saying that A[0] equals the original key, the original key is 2 so the list now looks like this:
2,65,88,9876,33,8.

See how the program got the number it was working with (2) and kept moving it back and back until it either encoutered a smaller number then it or the end of the loop.

Hope that helps, if you have any questions, just ask.

[leegeorg07]

hi again after reading your post i added some comments to the code could you read them to make sure of them and change them if they need it

def InsertionSort(A): # define the InsertionSort function
    for j in range(1, len(A)): # a for loop which starts j as 1
        key = A[j]# the key  is now A with j in it
        i = j - 1 # i is defined as j takeaway 1
        while (i >=0) and (A[i] > key): # a while loop to move the numbers
            A[i+1] = A[i] # please help with what this part does
            i = i - 1 # and the same with this bit
        A[i+1] = key # and again with this

x = [65,88,2,9876,33,8] # a list of numbers to rearrange
y = [65,88,2,9876,33,8,42,654,88,65,6] # another list of numbers to rearrange

InsertionSort(x) # sort the list called x
InsertionSort(y) # sort the list called y
print x # print the sorted list x
print y # print the sorted list y

thanks

[Stefano Mtangoo]

http://en.literateprograms.org/Insertion_sort_(Python,_arrays)

http://www.ece.uci.edu/~chou/py02/python.html

http://www.cs.luther.edu/~bmiller/Papers/paper20.pdf

Try and tell me what you think of them

[ZZucker]

Sometimes a test print will help you visualize what is going on:

def insertion_sort(qq):
    for j in range(1, len(qq)):
        key = qq[j]
        i = j - 1
        while (i >=0) and (qq[i] > key):
            qq[i+1] = qq[i]
            i = i - 1
        qq[i+1] = key
        # test print ...
        print qq

x = [65,88,2,9876,33,8]

insertion_sort(x)

print '-'*25

print x

"""
my output --->
[65, 88, 2, 9876, 33, 8]
[2, 65, 88, 9876, 33, 8]
[2, 65, 88, 9876, 33, 8]
[2, 33, 65, 88, 9876, 8]
[2, 8, 33, 65, 88, 9876]
-------------------------
[2, 8, 33, 65, 88, 9876]
"""

Just a note, I would reserve capitalized names for classes or global constants. Also, insertion sorts are pretty slow and inefficient when compared to merge and quick sorts.