Corning Community College
CSCS2330 Discrete Structures
Using the TIC-80 fantasy console simulator on your pi, implement a program that performs a sorting of a randomized list of values, both displaying an animation of the sort, along with timing and keeping track of the approximate number of steps needed to accomplish the task for variable numbers of non-animated runtimes.
The sorting algorithms I'd like for you to produce is that of:
You may want to look up the specifics on these algorithms to understand what their approach is, then to implement it.
Additionally, the entire class will be participating in documenting and filling out this project page. It is the responsibility of EACH class member to:
As with the projects before, `math.random()` can be used to generate random values for the array. It may also have a different purpose depending on how you approach this project. While there are many ways to show the algorithms… rinse and repeat, or do a brand new array… one can use `math.random()` to randomize which algorithm is used to sort the array upon each new initialized array.
Bubble Sort, sometimes called Sinking Sort, is a simple sorting algorithm that “repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.” For example, a sort of the array {5, 7, 3, 9, 2} would go as follows:
{5 7 3 9 2} -> {5 7 3 9 2}
{5 7 3 9 2} -> {5 3 7 9 2}
{5 3 7 9 2} -> {5 3 7 9 2}
{5 3 7 9 2} -> {5 3 7 2 9}
{5 3 7 2 9} -> {3 5 7 2 9}
{3 5 7 2 9} -> {3 5 7 2 9}
{3 5 7 2 9} -> {3 5 2 7 9}
{3 5 2 7 9} -> {3 5 2 7 9}
{3 5 2 7 9} -> {3 5 2 7 9}
{3 5 2 7 9} -> {3 2 5 7 9}
{3 2 5 7 9} -> {3 2 5 7 9}
{3 2 5 7 9} -> {3 2 5 7 9}
{3 2 5 7 9} -> {2 3 5 7 9}
{2 3 5 7 9} -> {2 3 5 7 9}
{2 3 5 7 9} -> {2 3 5 7 9}
{2 3 5 7 9} -> {2 3 5 7 9}
{2 3 5 7 9} -> {2 3 5 7 9}
{2 3 5 7 9} -> {2 3 5 7 9}
{2 3 5 7 9} -> {2 3 5 7 9}
{2 3 5 7 9} -> {2 3 5 7 9}
You will notice that, in this specific example, the algorithm had to sweep through 5 times in order to reach the final result. You will also notice that the complete sorting was finished after pass 4, but the algorithm did a 5th one as well. This is because the algorithm has to do one whole pass without doing a swap in order for it to be considered a successful sort. You will soon read about an algorithm (next algorithm) that is very similar, except far more robust and faster.
Selection sort takes a more direct piecewise approach to sorting - it will run through the list again and again, each time finding the lowest element and moving it to the beginning. Simply following that process would actually only ever perform a single action, though. The details of implementation more closely follow these ideas:
x = list.findLowestFrom(0); list.swap(x, list[0]); x = list.findLowestFrom(1); list.swap(x, list[1]); x = list.findLowestFrom(2); list.swap(x, list[2]); ...
By placing the lowest found node one index further along in the list each time, this ensures that the previously found lowest nodes are not displaced from their rightful position at the lowest index. Additionally, the searching in the list for the lowest node begins after the last placed node such that the same lowest node isn't found again and displaced to a later position.
A basic example of this would look like1):
{ 5 2 4 1 3 }
find lowest after 0
swap with index 0
{ 1 2 4 5 3 }
find lowest after 1
swap with index 1
{ 1 2 4 5 3 }
find lowest after 2
swap with index 2
{ 1 2 3 5 4 }
find lowest after 3
swap with index 3
{ 1 2 3 4 5 }
only one index remains, list must be in order
This certainly isn't the only approach, but that should give a basic illustration of what the animation may represent.
Insertion sort somewhat combines the incremental nature of bubble sort with the position-seeking ideas of selection sort. In insertion sort, the list is searched for the first element which is out of order (in our case, the first element which is lower than its predecessor) and then it is moved downward until it reaches a point where the element below it has a value which is lower than its own. Once that point is reached, it will continue searching for the initial situation of a lesser ancestor from the point which was reached in the previous operation and repeat until the last element is reached.
In order to meet project specifications, you must be sure to perform an animation of the sort. This is no difficult task. The simplest way to go about this is to simple use the print() function after every iteration of your sort. For example, regardless of what sort you are performing, they sort one number at a time. Intuitively, you should display the entire list after sorting the given number at that time. Because of this, you will want to make sure you are keeping track of your code, and are going to want to find where exactly each iteration of the sort is occuring.
print() is a very versatile tool; there are so many things to play around with and so many different arguments to take advantage of. For example, these are the arguments for print(): text [x=0 y=0] [color=12] [fixed=false] [scale=1] [smallfont=false]. The first three are pretty self-explanatory, but the latter are where things get interesting. The 'fixed' argument is referring to whether or not you desire a fixed letter width within your printed text. As the TIC80 Wiki puts it, “When set to true, the fixed width option ensures that each character will be printed in a 'box' of the same size, so the character 'i' will occupy the same width as the character 'w' for example.” Continuing, the 'scale' argument determines what scale you want your text on. As a esult, a scale bigger than 1 will produce similarly bigger text. But, you may ask, what happens if I want *smaller* text? Well that is where the 'smallfont' argument comes in. If set to true, the text font will be set to a smaller, fixed one. This is useful for displaying a large list of sorted and/or unsorted values in one row of text, rather than resorting to wrapping.
Alternatively, the rect() function serves as a nice geometrical alternative to print() for viewing of your lists as an assortment of rectangles. This is used in the format of rect( x, y, w, h, color), so if you were to loop through a list while shifting these rectangles' locations, it could serve to make a nice graphic to display the lists as they are being sorted.
https://github.com/nesbox/TIC-80/wiki
https://hub.xpub.nl/sandbot/PrototypingTimes/tic80-manual.html
https://www.lua.org/pil/contents.html
To submit the game file, our “tic” file, the file must be added to your lab46 somehow. This can be achieved through FTP software, such as FileZilla, or more easily by putting the file onto your Pi then pushing to your repo and pulling from lab46.
Of course, if you are using the TIC-80 application on your Pi then the file will exist there when saved.
To submit this project using the submit tool, run the following command at your lab46 prompt:
lab46:~/src/SEMESTER/DESIG/safX$ submit DESIG safX GAMENAME.tic Submitting DESIG project "safX": -> GAMENAME.tic(OK) SUCCESSFULLY SUBMITTED
NOTE: “GAMENAME” here is the name of your game. Please do not literally submit a tic file named “GAMENAME”, come up with a creative name for your game.
I'll be looking for the following:
78:saf1:final tally of results (78/78) *:saf1:no errors, program runs without issue in TIC-80 [13/13] *:saf1:specified algorithms are implemented and functional [39/39] *:saf1:metrics, timing of process is implemented, functional, shown [13/13] *:saf1:project page contributions as per project specifications [13/13]
Additionally: