Python代写：COMP3016 Fixed Sorting Network

发表于   |   分类于

练习由各种Sorting algorithm实现的网络相关编程。

Sorting algorithm

Goals

  • Understanding the sorting algorithms presented in class in further depth.
  • Introduction to fixed soting networks.
  • Compare code speed by comparing length.

Task 1: Fixed Bubble Sort

Introduction

A “sorting network” is a bunch of “compare and exchange” (also known as compare and swap) operations that are fixed and arranged in a particular sequence to sort a list of a particular length. These networks do not use any loops or recursion.

For example, a compare and exchange operation in python might look like:

1
2
if a_list[3] > a_list[4]:
  a_list[3], a_list[4] = a_list[4], a_list[3]

or

1
2
3
4
if a_list[3] > a_list[4]:
  temp = a_list[4]
  a_list[4] = a_list[3]
  a_list[3] = temp

Both of the above pieces of code do the same thing. The first method of swapping is available in Python, but doesn’t exist in many other programming languages.

To sort a list that’s always length 2, we can just use the following code:

1
2
3
4
def bubble2(a_list):
  if a_list[0] > a_list[1]:
	a_list[0], a_list[1] = a_list[1], a_list[0]
  return a_list

For sorting a list of length 2, we need exactly one compare/swap.

For sorting a list of length 3, using bubble sort, bubble sort in the first outer loop compares exchange index 0 with index 1, then index 1 with index 2. If the item at index 0 is the largest item, it will “bubble up” to index 2 during this iteration. That is, you need to use the bubble sort that iterates like this:

1
2
for bubble in range(0, n):
 for index in range(0, n - bubble - 1):

Then in the second iteration of the outer loop, it compares and exchanges index 0 with index 1.

This is the second bubble, but it doesn’t need to go all the way to the end, since the end is gauranteed to already have the largest item. So we can always sort a list of length 3 with the following code:

1
2
3
4
5
6
7
8
9
10
def bubble3(a_list):
  # bubble 0
  if a_list[0] > a_list[1]:
	a_list[0], a_list[1] = a_list[1], a_list[0]
  if a_list[1] > a_list[2]:
	a_list[1], a_list[2] = a_list[2], a_list[1]
  # bubble 1
  if a_list[0] > a_list[1]:
	a_list[0], a_list[1] = a_list[1], a_list[0]
  return a_list

Implementing Fixed Bubble Sort

Your goal for task 1 is to use the functions you made in task 1 to create a function fixed_bubble(size) which takes one argument. That argument will determine the length of the list that can be sorted. fixed_bubble(size) should output a file that contains a function that uses bubble sort to sort lists of length size. For examples, fixed_bubble(2) should create a bubble2.py that contains the above bubble2 function that takes a single argument (a list) to be sorted. Similarly, fixed_bubble(3) should create a bubble3.py that contains the bubble3 code above (or simlar code).

Your output code doesn’t have to be exactly like the above code, it can contain comments, you can use a different swap, etc. It doesn’t matter whether you use a_list[0] > a_list[1] or if you use a_list[1] < a_list[0], etc. It should just consist of a function with a big sequence of compare and exchange, however you want to write them and a return at the end. You can add comments or not. Adding comments in the output program can be helpful for debugging.

However your output sorting programs must not contain any loops, recursion, imports, or anything that gets Python to do loops or recurison or sorting for you. That means no for, while, map, etc. And definitely no sort or sorted or anything that sorts. Several of these keywords are checked by check1.py so be sure to avoid using names like list, or check1.py will fail. (Using a name like a_list or some_list is fine.) As always, check1.py can’t check for every way to do a loop or recursion in Python, but you still can’t have any in your code, regardless of what check1.py says.

Loops, for, while, sort, sorted, and recursion are 100% okay to put in your a3.py, but should never appear in the generated output programs like bubble4.py.

Additional example outputs are available in the files below: bubble4.py, etc.

Task 2: Bitonic Sort

Bitonic sort is a sorting routine that like Mergesort involves recursively splitting and merging. Unlike mergesort, it doesn’t require any extra space. Mergesort requires copying back and forth between at least two lists. Bitonic sort sorts everything while leaving it in the same list, like bubble sort does. So, it kind of combines the strengths of Bubblesort and Mergesort.

In order to do this, Bitonic sort sorts part of the lists in the wrong order (descending instead of ascending) before merging it into the correct order. The name (bi-tonic) comes from this. To help with this you should make a helper function in your a3.py called flip that takes a single argument, either > or < and flips it. So, flip(<) should return > and flip(>) should return <.

Another thing Bitonic sort has to do so that it doesn’t need extra lists is to recursively merge as well. So you will need two recursive functions: the recursive bitonic sort function, and the recursive bitonic merge function.

Like in mergesort, the recursive sort function will need to split the list in half and recursively call itself on both haves. However, you must do this by keeping track of indices (or indices and lengths), since you can’t split the list. You can’t use extra lists, since the entire idea of using bitonic sort is to avoid using extra lists.

For the recursive sort function you should consider the middle (where you split) to be half way through the indices available. For example, if the bitonic sort is called (recursively) with the start index 10 and the end index 21, it should split the list into two halves, 10 to 15 and 15 to 21. (Like in Python, end of all the ranges are exclusive, the highest index is actually 20.)

For the recursive merge function you should consider the middle (where you split) not half way, but instead with the upper half having a the biggest power of two number of items while still leaving some for the lower half. For example, if the bitonic merge is called (recursively) with the start index 10 and the end index 21, it should split the list into two halves, 10 to 13 and 13 to 21. This is because you have 11 items, and the greatest power of two less than 11 is 8, and so we give the upper half 8 items, and the remaining 3 to the lower half.

However, before splitting and recusively merging, you need to compare and swap the first three items with the last three items. So in this example, we’d compare and swap 10 with 18, 11 with 19, and 12 with 20. Then we’d recursively call our bitonic merge for 10 to 13 and 13 to 21.

To help with this you should make a helper function in your a3.py called greatest_power_of_two_less_than that takes a single argument, an integer >= 1. It should return the greatest power of two that’s less than that.

Examples:

1
2
3
4
greatest_power_of_two_less_than(4) == 2 # 2^1
greatest_power_of_two_less_than(5) == 4 # 2^2
greatest_power_of_two_less_than(100) == 64 # 2^6
greatest_power_of_two_less_than(32) == 16 # 2^4

Bitonic sort pseudocode:

  • a_list is a Python list
  • start is the start index >= 0
  • end is the end index <= len(a_list) direction is < or >
  • Base case: if start to end is only a single index, return
  • let middle be middle index between start and end, rounding down
  • call bitonic sort recursively from start to middle
  • call bitonic sort recursively from middle to end but with direction flipped
  • call bitonic merge from the start to end (using the original direction)

Bitonic merge psuedocode:

  • a_list is a Python list
  • start is the start index >= 0 end is the
  • end index <= len(a_list)
  • direction
  • Base case: if start to end is only a single index, return
  • let distance be the greatest power of two less than the length between start and end
  • let middle be end minus distance
  • for each index from start and stopping before middle:
    • compare and exchange index with index + distance
    • the compare (whether or not to exchange) should be done with the current value of direction
    • when direction is <, a_list[index] should be exchanged with a_list[index+distance] if a_list[index] is less than a_list[index+distance]
    • when direction is >, a_list[index] should be exchanged with a_list[index+distance] if a_list[index] is greater than a_list[index+distance]
  • call bitonic merge recursively from start to middle (direction is unchanged)
  • call bitonic merge recursively from middle to end (direction is unchanged)

You will probably want to use a third function to start your bitonic sort with start as 0 and end as len(a_list) and direction as >.

  • Here’s another reference for how this works
  • The wikipedia page also has some nice diagrams

Write a function in a3.py named bitonic that takes a single argument, a list to sort in ascending order.

Here are some example traces for bitonic and the way it calls recursively. The indentation indicates how many calls are on the call stack. (The recursion depth.) Your code does not have to print these, they are just to help you make sure your algorithm is correct.

Task 3: Fixed Bitonic Sort

Your goal for task 3 is to use the functions you made in task 1 and task 2 to create a function fixed_bitonic(size) which takes one argument. You should use your write_py function, but you’re free to make new bitonic functions based on the ones you made in task 4. That argument will determine the length of the list that can be sorted. fixed_bitonic(size) should output a file that contains a function that uses bitonic sort to sort lists of length size. For examples, fixed_bitonic(2) should create a bitonic2.py that contains the bitonic2 function that takes a single argument (a list) to be sorted. Similarly, fixed_bitonic(3) should create a bitonic3.py that contains the bitonic3 code.

Running and main()

To mark your code, we will run a different Python file in the same folder. Your python file must be named a3.py or it will not work! You can test your own code by using the check1.py from the download folder.

Main should be called it using the format:

1
2
if __name__ == "__main__":
  main()

No other code except CONSTANTS, functions, classes and comments should be unindented in your program.

Allowed Imports

1
2
3
4
5
from importlib import invalidate_caches
from importlib import import_module
from os.path import exists
from os import remove
from random import randrange

You are allowed to import any code generated by your write_py by using the load_function/import_module as long as that code doesn’t import anything.

You aren’t allowed to use any other libraries (besides the ones listed here) whether or not they come included with python.

No other imports are allowed.

Submission

  • Submit only your a3.py. Make sure it is named a3.py.
  • Late submissions will not be accepted.