Python

from importlib import invalidate_caches from importlib import import_module

   def load_function(name):
       """

       load_function - imports a module recently created by name
           and returns the function of the same name from inside of it

       name - a string name of the module (not including .py at the end)
       """

# invalidate_caches is necessary to import any files created after this file started!

       invalidate_caches()
       print(f"    Attempting to import {name}...")
       module = import_module(name)
       print(f"    Imported!")
       assert hasattr(module, name), f"{name} is missing from {name}.py"
       function = getattr(module, name)
       assert callable(function), f"{name} in {name}.py isn't a function"
       assert type(function) is type(

           load_function
       ), f"{name} in {name}.py isn't a function"
       return function						
Task 3: 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.						
Implementing Fixed Bubble Sort

Your goal for task 3 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 4: 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.						
Task 5: Fixed Bitonic Sort
Your goal for task 5 is to use the functions you made in task 1 and task 4 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.