0

For some reason, the cmd is taking 2 minutes to run a 18 line python program. I ran it again but it did not do anything. Can anyone tell me why it is taking that long? 

from array import *

file = open("IntegerArray.txt" , "r")

input_array = array('i')

for line in file:
    c = int(line)
    input_array.append(c)

top_array = input_array[:len(input_array)//2]
bottom_array = input_array[len(input_array)//2:]

inversion = 0
max_index = len(top_array) 

for i in range(0, max_index):
    for j in range(i + 1, max_index):
        if top_array[i] > top_array[j]:
            temp = top_array[i]
            top_array[i] = top_array[j]
            top_array[j] = temp
            inversion = inversion + 1
print "inversion = ", inversion
Avi P.
  • 3
  • 5
  • How big is the input? – James Jul 12 '15 at 22:36
  • about 50,000 numbers – Avi P. Jul 12 '15 at 22:37
  • 1
    You can't really judge a program's running time by how many lines it is. Your code has a doubly-nested loop, so if your input is large, you should expect to take a while. – James Jul 12 '15 at 22:38
  • I know that it is big but I don't see how it would take that long – Avi P. Jul 12 '15 at 22:38
  • Anyway, thanks for answering – Avi P. Jul 12 '15 at 22:40
  • In your case, you are running the code inside the inner loop O(n^2) times. For n=50,000, this is 2500000000 times. (actually it is 2500000000/2 times, but still very big) – James Jul 12 '15 at 22:40
  • You could speed up your inner-loop by using `top_array[i], top_array[j] = top_array[j], top_array[i]` to swap the two values. – martineau Jul 12 '15 at 22:54
  • See http://stackoverflow.com/questions/337664/counting-inversions-in-an-array – smci Jul 12 '15 at 23:01
  • It would be _much_ faster if you just used the built-in `sorted()` function to sort `top_array` — i.e. `top_array = array('i', sorted(top_array))` although that won't tally an `inversion` count for you. – martineau Jul 12 '15 at 23:07

1 Answers1

0

Not related to the time, but you can simplify this:

        temp = top_array[i]
        top_array[i] = top_array[j]
        top_array[j] = temp

to

top_array[i], top_array[j] = top_array[j], top_array[i]
joel goldstick
  • 4,393
  • 6
  • 30
  • 46