Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
<WRAP centeralign round box>
<WRAP><color red><fs 200%>Corning Community College</fs></color></WRAP>
<WRAP><fs 150%>CSCS2330 Discrete Structures</fs></WRAP>
</WRAP>

======PROJECT: SORTING ALGORITHM FUN (SAF1)======

=====Objective=====

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:

  * bubble sort
  * insert sort
  * selection sort

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:

  * ask copious, clarifying questions (so you can better add content)
  * craft a coherent and organized document, with information located under pertinent headings
  * explain the fundamentals of the process, conceptual background, algorithmic approach, and you can even suggest particulars related to TIC-80 (certain functions that might prove useful- individual, unrelated snippets to do things like capturing time, or displaying text, etc.)
  * to get full credit, each individual that submits must perform no fewer than 4 changes to this document (as viewable from the wiki revision system). Failure to do so will result in documentation penalties being applied.

=====Specifications=====

====Process====

==Randomness in Lua==

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==

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:
<code>
{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}
</code>
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==

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:

<code>
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]);

...
</code>

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 like(("lowest after" is inclusive; "lowest after 0" means lowest at or after 0)):

<code>
{ 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
</code>

This certainly isn't the only approach, but that should give a basic illustration of what the animation may represent.

==Insertion Sort==

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.

====Display====

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. 

==A Note on the Print Function==

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.

=====References=====

https://github.com/nesbox/TIC-80/wiki

https://hub.xpub.nl/sandbot/PrototypingTimes/tic80-manual.html

https://www.lua.org/pil/contents.html

https://en.wikipedia.org/wiki/Bubble_sort

https://github.com/nesbox/TIC-80/wiki/palette
=====Submission=====

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:

<cli>
lab46:~/src/SEMESTER/DESIG/safX$ submit DESIG safX GAMENAME.tic
Submitting DESIG project "safX":
    -> GAMENAME.tic(OK)

SUCCESSFULLY SUBMITTED
</cli>

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:

<code>
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]
</code>

Additionally:
  * Solutions not abiding by **SPIRIT** of project will be subject to a 25% overall deduction
  * Solutions not utilizing descriptive why and how **COMMENTS** will be subject to a 25% overall deduction
  * Solutions not utilizing **INDENTATION** to promote scope and clarity will be subject to a 25% overall deduction
  * Solutions lacking **ORGANIZATION** and are not easy to read (within 90 char width) are subject to a 25% overall deduction
Lab46 Wiki

User Tools

Site Tools

Page Tools
