Count inversion in python (for large integer array)

Question

I making a program for count inversion in pyhton and using python27 for the same. I have implement the alogorithm using divide and conquer technique(merge sort trick). My program runs fine for an input array of size uptill 100 (that's the max I could verify). Now i tested my program on an input array of size 50,000 and 1,00,000 but how ever i could not get correct answers. I have pasted my code below, kindly point out any possible mistake:

    f=open('forum.txt')
    a=[]
    s=1
    for line in f:
        a.append(line)





def CountInversion(IntegerArray):
_count=0
lc=0
rc=0
RightArray=[]
LeftArray=[]
if len(IntegerArray)>1:
        LeftArray,lc=CountInversion(IntegerArray[:len(IntegerArray)/2])
        RightArray,rc=CountInversion(IntegerArray[len(IntegerArray)/2:])
elif len(IntegerArray)==1:
    return IntegerArray,0
ResultArray=IntegerArray
i=0
l=len(ResultArray)
j,k=0,0
for i in range(0,l):
    if j<len(RightArray) and k<len(LeftArray):
        if RightArray[j]<LeftArray[k]:
            ResultArray[i]=RightArray[j]
            j += 1
            a=(len(LeftArray)-k)
            _count = _count + a    
        else:
            ResultArray[i]=LeftArray[k]
            k += 1
elif j<len(RightArray):
    ResultArray[i]=RightArray[j]
        j += 1
elif k<len(LeftArray):
        ResultArray[i]=LeftArray[k]
        k += 1          
return ResultArray,(_count+lc+rc)

arr,b=CountInversion(a)

print ('end of inversions')

print b

I also ran the code given by J.F. Sebastian in this post, but the results are same(answers are correct for small input but not for input array of size 50000 or 1,00,000)

That is barely readable, but you can efficiently count inversions by implementing a merge sort yourself with a tiny modification (which might be what this code is trying to do). — mmgp, Feb 09 '13 at 02:13
the python script is this http://dl.dropbox.com/u/106712820/backup.py — nishant mehta, Feb 09 '13 at 03:17
also the input file is http://dl.dropbox.com/u/106712820/forum.txt — nishant mehta, Feb 09 '13 at 03:17
also i tried to run the code for this problem given by J.F. Sebastian in [this](http://stackoverflow.com/questions/2987605/minimum-number-of-swaps-needed-to-change-array-1-to-array-2/2989341#2989341) thread. But i am still not able to get the correct answer. Maybe there is some problem with my compiler/i am using a substandard version of python....Kindly suggest — nishant mehta, Feb 09 '13 at 03:20
How are you determining if you have a good result for the longer sets? Do you have known results that you're comparing against? Also, the `forum.txt` file you've linked contains numbers (one per line) but the file-reading logic you show in your code leaves the values as strings. This may result in different sorting that you expect (e.g. `'11'` sorting ahead of `'2'`)! — Blckknght, Feb 09 '13 at 03:46

score 0 · Accepted Answer · answered Feb 09 '13 at 03:48

Your first problem is that you have inconsistent indentation. On a few lines you're using tabs instead of spaces, which is a very bad idea. Indentation is significant in Python, so it is easy to make errors if you don't watch out.

The second problem that I think you're having is that you're comparing strings, rather than numbers. Python is perfectly happy to sort strings, but it will use lexicographical orering, which can be unexpected when applied to integers encoded as strings. For example, the string "11" will be sorted ahead of the string "2", since it's first character 1 comes before 2 in the ASCII character set (and also in Unicode).

As I asked in a comment, it's not clear how you're determining that your code isn't working correctly. It may be that simply fixing the issues I described above will fix the problems you're having. If they do not, please explain how you're determining that your results are invalid and I'll try to update this post with further suggestions.

thanks a lot, it worked!!! i just parsed the string to int and populated the array. was struggling on it since 3 days, thanks again!! — nishant mehta, Feb 09 '13 at 08:21

score 0 · Answer 2 · answered Oct 01 '13 at 19:57

0

The problem is solved by parsing string to int and populating the array

answered Oct 01 '13 at 19:57

nishant mehta

109
1
10

This answer would be greatly improved by adding some sample code. – Bob Gilmore Oct 01 '13 at 20:21

Count inversion in python (for large integer array)

2 Answers2