Skip to content

Instantly share code, notes, and snippets.

@hbillings
Created March 26, 2012 02:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hbillings/2202578 to your computer and use it in GitHub Desktop.
Save hbillings/2202578 to your computer and use it in GitHub Desktop.
Recursively find inversions, then merge and find split inversions
#!usr/bin/python
import csv
num_reader = csv.reader(open('some_file.txt','rb'), delimiter="\n")
nums = list(num_reader)
# testing list so we don't have to use a huge file
# nums = [6,8,3,5,1,2,9,7,4,12,10,11]
i, j, left_inv, right_inv = 0, 1, 0, 0
left, right, left_sorted, right_sorted = [], [], [], []
for index, item in enumerate(nums):
if index < len(nums)/2:
left.append(int(item[0]))
else:
right.append(int(item[0]))
# for starting at the end of a sorted array to compare items
def enumerate_reversed(sorted_array):
for index in reversed(xrange(len(sorted_array))):
yield index, sorted_array[index]
def count_and_sort(some_array, inv_count, sorted_array, i, j):
print "Recursively counting and sorting arrays..."
while j <= len(nums)/2:
counter = i
for index, item in enumerate_reversed(sorted_array):
if item > some_array[i]:
counter = index
inv_count += 1
else:
break
sorted_array.insert(counter, some_array[i])
i += 1
j += 1
return inv_count
def merge(left, right, inv_count):
print "Merging..."
invs = []
i, j = 0, 0
while len(invs) < (len(left) + len(right)):
if i < len(left) and j < len(right):
if left[i] < right[j]:
invs.append(left[i])
i += 1
else:
invs.append(right[j])
# the number of inversions is equal to the total number of items minus the current position
inv_count += (len(left) - i)
j += 1
elif i < len(left) and j == len(right):
invs.append(left[i])
i += 1
elif j < len(right) and i == len(left):
invs.append(right[j])
j += 1
print "Final inversion count: " + str(inv_count)
left_inv = count_and_sort(left, left_inv, left_sorted, i, j)
right_inv = count_and_sort(right, right_inv, right_sorted, i, j)
inv_count = left_inv + right_inv
merge(left_sorted, right_sorted, inv_count)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment