Number of comparisons in insertion sort

问题:

In this program, I want to calculate the number of data comparisons in the insertion sort, but my code is not working as I expected.

def insertionSort(list):
    numOfComp = 0
    for i in range(1,len(list)):
        value = list[i]
        j = i - 1
        while j>=0:
            if value < list[j]:
                list[j+1] = list[j]
                list[j] = value
                j = j - 1
                numOfComp += 1
            if value >= list[j]:
                numOfComp += 1
                j = j - 1
            else:
                break
    print("Number of data comparisons:",numOfComp)
    print("Sorted list:",list)

回答1:

the problem is

if value >= list[j]:
     numOfComp += 1
     j = j - 1

If value >= list[j] you can and should simply exit your while loop and stop further comarisons

Also you are repeating the comparisons twice See the following refined code

def insertionSort(list):
    numOfComp = 0
    for i in range(1,len(list)):
        value = list[i]
        j = i - 1
        while j>=0:
            if value<list[j]:
                flag=True
            else :
                flag=False
            numOfComp += 1
            if flag:
                list[j+1] = list[j]
                list[j] = value
                j = j - 1
            else:
                break
    print("Number of data comparisons:",numOfComp)
    print("Sorted list:",list)

回答2:

Don't forget that loop header executed +1 more then the loop body, which we call the exit-condition, take this example:

S = 0;
for(int i = 0; i < 5; i++) {
    S++;
}

The S++ runs 5 times, however the i < 5 runs 6 times, the last one is to check if i < 5, will find the false and exit the loop.