Insertion Sort Comparison Counter

yasara 0
Viewed 27

i am trying to get the comp for the following sort however for "data1" it is giving 15 when the expected no is supposed to be 19. What am I doing wrong? (according to http://watson.latech.edu/book/algorithms/algorithmsSorting2.html, data1 is supposed to have 19 comparisons)

def insertionSorts(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 (numOfComp)


data1 = [10, 30, 80, 70, 20, 60, 40]
insertionSorts(data1)
print(data1)
print('No.of Comparisons: ', totalcompi)
print()
python
1 Answers

You are sorting the wrong list. The input producing the table shown in your link is [50, 10, 30, 80, 70, 20, 60, 40] (as suggested by the preceding page as well).

The table in your link starts with the initial list split into a sorted portion (consisting trivially of the first element of the full input) and an unsorted portion (the remaining items that have to be inserted into the sorted portion). You are only sorting that unsorted portion in your code.

chepner0
Related