Created
July 21, 2017 05:10
-
-
Save jhyang12345/3e0bd9e982e3b014f1b92b72bbcb33b2 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import random, sys | |
def bubblesort(a): | |
swaps = 0 | |
for x in range(1, len(a)): | |
for i in range(0, len(a) - x): | |
if(a[i] > a[i + 1]): | |
swaps += 1 | |
buf = a[i] | |
a[i] = a[i + 1] | |
a[i + 1] = buf | |
return swaps | |
def merge(arr, left, right): | |
i = 0 | |
j = 0 | |
ret = 0 | |
while( i < len(left) or j < len(right)): | |
if(i == len(left)): | |
arr[i + j] = right[j] | |
j += 1 | |
elif j == len(right): | |
arr[i + j] = left[i] | |
i += 1 | |
elif left[i] <= right[j]: | |
arr[i + j] = left[i] | |
i += 1 | |
else: | |
arr[i + j] = right[j] | |
ret += len(left) - i | |
j += 1 | |
return ret | |
def invcount(arr): | |
if(len(arr) < 2): return 0 | |
m = (len(arr) + 1) // 2 | |
left = list(arr[:m]) | |
right = list(arr[m:]) | |
return invcount(left) + invcount(right) + merge(arr, left, right) | |
arr = list(range(1, 8)) | |
random.shuffle(arr) | |
arr2 = list(arr) | |
print(arr) | |
print(invcount(arr)) | |
print("Done", arr) | |
print(arr2) | |
print(bubblesort(arr2)) | |
print("Done", arr2) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment