Solution to Array-Inversion-Count by codility
Question: https://codility.com/demo/take-sample-test/array_inversion_count Question Name: ArrayInversionCount
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | def mergesort( aList, first, last ): ''' Modified merge sort algorithm. Record the inversion count during sort. ''' mid = ( first + last ) / 2 if first < last: # Recursive calling left_inver = mergesort( aList, first, mid ) right_inver = mergesort( aList, mid + 1, last ) else: # Terminate condition return 0 first_index = first # The index for the left part second_index = mid + 1 # The index for the right part temp = [0] * (last-first+1) # To hold the sorted content temp_index = 0 merge_inver = 0 # Number of inversion in merging while first_index <= mid and second_index <= last: if aList[first_index] <= aList[second_index]: # Less index indicates less value. No inversion. temp[temp_index] = aList[first_index] first_index += 1 else: # Greater index has less value. Inversion exists. # For exampe: # [ 4, 5, 2, 3 ] # | Left part | |Right Part| # and first_index = 1, second_index = 3, mid = 2 # We need the item "2" to be the position 0. So it # has to pass all the unwritten items in left part. # Here these unwritten items are "4" and "5". So # two more inversions are involved. # In general, the left part is sorted. So all the # elements, being and after first_index, are greater # than element in position second_index. AND all of # them have less indexes. As the result, # there are mid-first_index+1 new reversions. temp[temp_index] = aList[second_index] second_index += 1 merge_inver += mid - first_index + 1 temp_index += 1 if first_index != mid+1: # Some element in the left part left. They have less # indexes, but greater values. Inversion involves. # BUT these inversions have already been counted. while first_index <= mid: temp[temp_index] = aList[first_index] first_index += 1 temp_index += 1 if second_index != last+1: # Some element in the right part left. They have both # greater indexes and values than all in the left part. # No inversion is involved. while second_index <= last: temp[temp_index] = aList[second_index] second_index += 1 temp_index += 1 # Rewrite the sorted content into the original array aList[first:last+1] = temp[:] return merge_inver + left_inver + right_inver def solution(A): return mergesort( A * 1, 0, len(A)-1) |
UPDATE on July 18, 2014: Thanks to @Andrew, there is another solution with Binary Indexed Tree. UPDATE on October 8, 2014: Thanks to @Piotrek Martynowicz, there was a bug for the statement: “computes the … Read More »