This code works as follows : It accepts number of test case T. For each test case, it accepts length of sequence of integers N and the sequence (or list) itself L.
The goal is to sort the list by checking every three consecutive elements, but only comparing the ends. L[i] and L[i+2]. If the right side is less than left one, then these two have to be swapped. This algorithm will continue until nothing can be swapped.
The problem is, my code works for N < 100. Also work for N larger but very slow, exceeded the time limit which is 20 secs.
If the list ended up sorted correctly, the output must be 'OK'.
If the list ended up not sorted, the output must be the first index in which the next index has element less than it.
This is part of google code jam 2018 qualificatiom round, finished already.
How to optimize this in Python..? What are the arguments? Thanks.
T = input() N =  L =  output =  for t in range(T): N.append(input()) L.append(raw_input()) def trouble(l, n): repeat = True while repeat: repeat = False for index in range(0,n-2): if l[index] > l[index+2]: repeat = True dum = l[index:index+3] l[index] = dum[-1] l[index+2] = dum del dum return l def search(l, n): for i in range(n): if l[i] > l[i+1]: return i for i in range(T): l = L[i].split() l = [int(num) for num in l] res = trouble(l, N[i]) if res == sorted(l): output.append('OK') else: output.append(search(l, N[i])) for t in range(T): print('Case #'+str(t+1)+': '+str(output[t]))