notes:discrete:fall2021:projects:saf2
Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| notes:discrete:fall2021:projects:saf2 [2021/10/21 01:38] – Added basic information on Slow Sort smalik3 | notes:discrete:fall2021:projects:saf2 [2021/10/21 03:16] (current) – Added direct link to References in Slow Sort algorithm conclusion smalik3 | ||
|---|---|---|---|
| Line 7: | Line 7: | ||
| =====Objective===== | =====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. | 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. | ||
| Line 93: | Line 94: | ||
| ===Slow Sort=== | ===Slow Sort=== | ||
| - | Similar to Merge Sort and Quick Sort, Slow Sort uses a divide and conquer technique with one catch: it is // | + | Similar to Merge Sort and Quick Sort, Slow Sort uses a divide and conquer technique with one catch: it is // |
| + | 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 [[https:// | ||
| ====Display==== | ====Display==== | ||
| + | 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:// | ||
| + | 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. | ||
| =====References===== | =====References===== | ||
| Line 108: | Line 116: | ||
| https:// | https:// | ||
| + | http:// | ||
| + | |||
| + | https:// | ||
| + | |||
| + | https:// | ||
| =====Submission===== | =====Submission===== | ||
notes/discrete/fall2021/projects/saf2.1634780336.txt.gz · Last modified: 2021/10/21 01:38 by smalik3
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
