3
\$\begingroup\$

Is there any way of counting how many shifts would it take to count shifts while doing insertion sort? This is a Hackerrank problem. Here's my solution, but it takes more than 16 seconds.

counts = []
for _ in range(int(input())):
    size = int(input())
    ar = list(map(int, input().split()))
    count = 0
    for i in range(1, len(ar)):
        j = i
        while j >= 1 and ar[j] < ar[j-1]:
            ar[j], ar[j-1] = ar[j-1], ar[j]
            j -= 1
            count+=1
    counts.append(count)
for c in counts: print(c)

Insertion Sort is a simple sorting technique which was covered in previous challenges. Sometimes, arrays may be too large for us to wait around for insertion sort to finish. Is there some other way we can calculate the number of times Insertion Sort shifts each elements when sorting an array?

If ki is the number of elements over which ith element of the array has to shift then total number of shift will be k1 + k2 + … + kN.

Input: The first line contains the number of test cases T. T test cases follow. The first line for each case contains N, the number of elements to be sorted. The next line contains N integers a[1],a[2]…,a[N].

Output: Output T lines, containing the required answer for each test case.

That's the problem. Is there any way I could optimize my solution?

\$\endgroup\$
1

1 Answer 1

3
\$\begingroup\$

Insertion sort is an O(n2) algorithm. There's only so much you can do to optimize it.

This is a bit of trick question. It doesn't actually ask you to sort the arrays in question; it just asks you to count the number of shifts involved. So, for each element to be "inserted", just count the number of preceding elements that have a larger value.

Stylistically, your program should be modularized. Each of the T test cases is independent, so isolate each test case in a function. You probably don't have to buffer the results, either — just print the result from each test case as soon as you have the answer.

\$\endgroup\$
2
  • \$\begingroup\$ you mean to remove those swaps? \$\endgroup\$ Mar 15, 2014 at 13:05
  • \$\begingroup\$ Yes, that's right. Hint \$\endgroup\$ Mar 15, 2014 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.