Last active
May 31, 2016 16:28
-
-
Save madmann91/b81c75c4fe0f41db47ac5ce52bc641f8 to your computer and use it in GitHub Desktop.
Creates a sequence of compare-swap operations that perform a sort.
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
#!/usr/bin/python3 | |
import sys | |
# Returns a list of compare-swap tuples that merges two lists | |
def gen_merge(a, b): | |
return [(x, y) for x in a for y in b] | |
# Returns a list of compare-swap tuples that performs a merge sort | |
# Generates n^2/2 - n/2 = O(n^2) compare-swaps | |
def gen_sort(l): | |
n = len(l) | |
if n <= 1: | |
# No comparisons are required to sort less than one element | |
return [] | |
if n == 2: | |
# Comparisons to sort two elements | |
return [(l[0], l[1])] | |
m = n // 2 | |
left, right = l[:m], l[m:] | |
# Comparisons to sort the left segment | |
cmp_left = gen_sort(left) | |
# Comparisons to sort the right segment | |
cmp_right = gen_sort(right) | |
# Comparisons to do the merge | |
cmp_merge = gen_merge(left, right) | |
return cmp_left + cmp_right + cmp_merge | |
def main(): | |
if len(sys.argv) != 2: | |
sys.exit("Number of elements expected") | |
n = int(sys.argv[1]) | |
for x, y in gen_sort(range(0, n)): | |
print("cmp_swap(" + str(x) + ", " + str(y) + ")") | |
if __name__ == "__main__": | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment