CODEWITHSUNDEEP
algorithmsorting
LTim
LTim

Reputation: 493

Difference between comparisons and swaps in insertion sort

Given below is a pseudocode of insertion sort algorithm applied on array A (zero-based indexing). def compare(a, b) : if a > b return 1 else return -1

    for i : 1 to length(A)
    j = i - 1
    while j > 0
           if compare(A[j-1], A[j]) > 0
                swap(A[j], A[j-1])
                j = j - 1
           else break

Given an array A of integers , find difference between number of compare function calls and number of swap function calls by above algorithm when applied on A.

Let us take an example with A = {1, 2, 4, 3}. If we apply insertion sort as above on A we call sequeunce of compare and swap functions in following order

compare (A[0], A[1])
compare (A[1], A[2])
compare (A[2], A[3])
swap       (A[2], A[3])
compare (A[1], A[2])

Here compare function is called 4 times, swap function is called 1 time. The answer is 4-1 = 3.

I need to find the difference optimally without running the actual insertion sort algorithm which takes O(n^2).

Upvotes: 2

Views: 2776

Answers (2)

DAle
DAle

Reputation: 9117

For every i from 2 to length(A) the number of compare calls will be one more than the number of swap calls besides the situation where the current element is minimal among all elements from 1 to i (in this situation we exit from the loop when j becomes 0). The answer will be length(A)-1 - minimal number occurrences.

minElement = A[1] // one-based array
result = length(A) - 1
for i = 2 to length(A)
    if A[i] < minElement 
        minElement = A[i]
        result = result - 1

Upvotes: 1

sndpkpr
sndpkpr

Reputation: 639

put a counter in while loop and another in if condition. The subtraction of these two will give the answer.

Upvotes: 0

Related Questions