trjhtr

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[0]
 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]))

With python 2.7, you have xrange. The improvement in performance might be minimal (but an improvement nonetheless):

The advantage of xrange() over range() is minimal (since
xrange() still has to create the values when asked for them) except
when a very large range is used on a memory-starved machine or when
all of the range’s elements are never used (such as when the loop is
usually terminated with break).

Split your $ L $ and use map as soon as possible.

L.append(map(int, raw_input().split()))

Swapping in python is as easy as:

a, b = b, a

No need to allocate a temporary dummy (and del it later):

if l[index] > l[index + 2]:
 repeat = True
 l[index], l[index + 2] = l[index + 2], l[index]

Now, for the time limit issue, since you know that you are actually sorting the even and odd indexes sublists disjointly; splice your $ L $ and sort those. Then, reattach them both by weaving them together.

# L has been read from user
l_even = sorted(l[::2])
l_odd = sorted(l[1::2])

and then join them together.