Time optimization of counting shifts in insertion sort

Question

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?

• leandrotk: My code did 0.04s: github.com/LeandroTk/Algorithm_DataStructure/blob/master/… I think your code takes more than 16 seconds, because of the 3 nested loops.. (n³).

Answer 1

Insertion sort is an O(n²) 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.

• Mohammad Areeb Siddiqui: you mean to remove those swaps?
• 200_success: Yes, that's right. Hint