Skip to content

Instantly share code, notes, and snippets.

@madmann91
Last active May 31, 2016 16:28
Show Gist options
  • Save madmann91/b81c75c4fe0f41db47ac5ce52bc641f8 to your computer and use it in GitHub Desktop.
Save madmann91/b81c75c4fe0f41db47ac5ce52bc641f8 to your computer and use it in GitHub Desktop.
Creates a sequence of compare-swap operations that perform a sort.
#!/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