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?
