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:

• a sort of your choosing
  • not one you've already been asked to do or have done
  • unique from what others have chosen (so each person can author a blurb about it on the wiki)
• merge sort
• quick 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.

Merge Sort is regarded as one of the most efficient sorting algorithms known. It is an algorithm based on comparison sort logic. The logic goes as follows:

-Divide the unsorted list into *n* sub-lists, each containing one element.
-Repeatedly merge sub-lists to produce new sorted sub-lists until only one remains.

In simple terms, the algorithm repeatedly separates the list into sub-lists until each sub-list has only two integers. Then, it compares the two (and therefore sorts the sub-list). It keeps going through this, recursively, until ending in a sorted, full list. If you are still confused on how exactly this works, a helpful graphic is included in the Wikipedia page provided below.

The Process of the Cocktail Sort is similar to that of the Bubble Sort, but with a bit of added efficiency and fun. The first passthrough is identical to that of a Bubble Sort, comparing adjacent numbers and pushing the greater one up in the list.

Once we get to the second passthrough, things change a bit from the Bubble Sort's process. This time we descend the list, disregarding the last element, seeing as the greatest list element should be in this position already. This passthrough will compare adjacent values and move the lesser value towards the start of the list, until the least value is placed at the beginning.

Once again, we ascend the list, disregarding the sorted element(s) and repeat this process until the sorted portions of the top and bottom of the list meet in the middle, resulting in a fully sorted list.

A morbidly memory inefficient algorithm, the index sort was a sudden idea that popped into my head as I was about to implement a different sort of my choice, but then this custom one quickly won me over. The use case of this sort is one where the desired output represents the full range of represented values ordered, but not repeats. This way, only the appearing numbers are sorted, but the full wealth of dataset information is more easily compartmentalized (that makes it sound like a feature, right?).

This sort accepts a dataset as input, and creates a secondary array with a size equal to that of the largest value in the dataset minus one. Then, it loops over the original dataset, placing each value at its own index minus one. Next, it will remove any “holes” in the secondary array, meaning it will be narrowed down to only values - no empty indices. To finish sorting, it simply writes over the original array with the secondary array.

Here is a modified implementation example:

index(int[] dataset) {
  // Allocate subset
  subArr[dataset.getLargest()-1];
  // Populate subset
  for (i=0;i<dataset.size;i++) {
    val = dataset.get(i);
    subArr[val-1] = val;
  }
  
  // Rewrite original array
  dataset.clear();
  for (i=0;subset.size > 0;i++) {
    num = subArr[0];
    if (num != NULL) {
      dataset[i] = num;
    } else {
      i--;
    }
    subArr.removeFirst();
  }
}

And an output example:

Dataset IN:  { 1, 5, 6, 8, 3, 3, 0, 1, 9 }
Subarray:    { 0, 1,  , 3,  , 5, 6,  , 8, 9 }
Dataset OUT: { 0, 1, 3, 5, 6, 8, 9 }

As can be seen based on the fact that the subarray outsizes the ingoing dataset in the example, as dataset values become larger, this approach becomes infinitely less useful, but is actually very, very fast in smaller, more controlled applications like mine, where the dataset simply contains a no-repeat set of values from 1-datasetSize, as it only needs to perform 1 read and 2 write operations per datapoint regardless of position or value.

Also known as Stupid Sort, this algorithm is very similar in concept to Insert Sort, in the sense that it parses through the list one element at a time. It goes through the list, starting with a position of 0 up until the length of the list, comparing each element to the last. If the current is less than the previous, they are swapped, and the position decreases by one. The algorithm finishes when the position equals that of the length of the list.

Similar to Merge Sort and Quick Sort, Slow Sort uses a divide and conquer technique with one catch: it is extremely slow. More or less a gimmick sorting algorithm that should not be applied when efficiency is required, but is very interesting to see and understand how it works. Please never seriously use this algorithm! If you use it, use it for only 2 to 25 elements roughly.

Slow Sort is given three parameters: array, initial index, and ending index. First working by making sure that the initial index is smaller than the ending index, if not the algorithm will not run. Once that is out of the way, the middle index (roughly between initial index and ending index) is calculated and stored. Then the algorithm works recursively so sort from the initial index to middle index, then from one after the middle index to the ending index.

It then does a comparison of values, seeing if the element at the middle index of the array is greater than the element at the ending index of the array. If this condition turns out true then both elements are swapped. After this, we do one last sort… and this one is the kicker. Now we will recursive call our Slow Sort algorithm with the same table, same initial index, and the ending index minus one.

The combination of all these recursive calls and minor swaps is what results in the extremely slow speeds of this algorithm. For more information check out the paper written on this algorithm in References below.

Displaying the output in TIC80 is very simple. There is a print() function in LUA that is used to display output to the screen. With the print function you can provide the exact X and Y coordinates that you would like to display your output. Print also supports providing a numerical character that is associated with a specific color, meaning you can have all different colors of output. You can see the numbers that are associated with specific colors here https://github-wiki-see.page/m/nesbox/TIC-80/wiki/palette.

With the series of safX projects in mind, it is important to note that we must display our output after every iteration of a sort. So we must show how each number in the list is sorted at a time. If you have a list of ten numbers, you are likely going to want to show at least 10 iterations of the sort. Depending on the algorithm at hand, you may have a different amount of sorts displayed.

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

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

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

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

http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=1F04699107977CB136067BB474E07146?doi=10.1.1.116.9158&rep=rep1&type=pdf

https://www.youtube.com/watch?v=Hoixgm4-P4M - Quick Sort

https://www.youtube.com/watch?v=4VqmGXwpLqc - Merge Sort

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:saf2:final tally of results (78/78)
*:saf2:no errors, program runs without issue in TIC-80 [13/13]
*:saf2:specified algorithms are implemented and functional [39/39]
*:saf2:metrics, timing of process is implemented, functional, shown [13/13]
*:saf2:project page contributions as per project specifications [13/13]

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