CODEWITHSUNDEEP
pythonalgorithmpython-3.xcomparisoninsertion-sort
a_guy
a_guy

Reputation: 23

Python 3: Insertion Sort comparisons counter

I need to add a counter of total comparisons for my Insertion Sort program but I don't know why I'm getting a total of 0 comparisons!

I know that the comparisons output should be 15 (for my specific array) not 0.

This is my code so far:

def insertionSort(values):
    k = 0
    n = len(values) - 1
    comparisons = 0
    while k+1 <= n:
        i = k
        while values[i] > values[i+1]:
            temp = values[i]
            values[i] = values[i+1]
            values[i+1] = temp
            comparisons += 1 #I think this is wrong
        k = k + 1
    return comparisons, values

What am I doing wrong?

Upvotes: 2

Views: 10089

Answers (2)

Vivek Kalyanarangan
Vivek Kalyanarangan

Reputation: 9081

I just checked your code and its not serving the purpose for sorting [7,5,4,6].

Here's a modified version - 

def insertionSort_mod(values):
    k = 0
    n = len(values) - 1
    comparisons = 0
    while k+1 <= n:
        i = k+1
        curr_val = values[i]
        comparisons += 1
        while i>0 and values[i-1] > curr_val:
            values[i] = values[i-1]
            i=i-1
            comparisons += 1
        values[i] = curr_val
        k = k + 1
    return comparisons, values

print insertionSort_mod( [1, 2, 3, 55, 5, 6, 8, 7, 9, 111])

Outputs this:

(15, [1, 2, 3, 5, 6, 7, 8, 9, 55, 111])

In your context k+1 should be the current index so i should be k+1 and should be compared to the previous value i-1

Upvotes: 1

SaiKiran
SaiKiran

Reputation: 6504

Hope this works

def insertion(a,length):
    count=0
    for i in range(1,length):
        key=a[i]
        jj=i
        while(jj>0 and a[jj-1]>key):
            a[jj]=a[jj-1]
            jj=jj-1
            count += 1
        a[jj]=key
    print count

The no. of swaps would be equal to the number of elements for which you shift the elements using the while loop. So, you could use a flag variable inside the while loop, to check if the loop runs for each element, and increase the counter variable by 1, every time the flag variable shows swapping.

Upvotes: 1

Related Questions