Links to Webapp:
https://csalgs.herokuapp.com/click
Abstract
The purpose of this project was to create a tool that students in the field of computer science. Through this program, users can learn and get better at visualizing the functionalities of various sorting algorithms. This app allows students to play in two different game modes with 4 different sorting algorithms.
Introduction
In many introductory and intermediate computer science courses, students are introduced to various sorting algorithms; each involve different methods of sorting, vary in complexity, and incorporate worst-case scenarios. When students first encounter these algorithms, it is often hard for them to remember what each algorithm does. For example, it can be easy to confuse insertion sort with selection sort because both types of algorithms utilize finding the minimum and maximum.
On the web, there are many sources where students can visualize the algorithms and get explanations of the steps each algorithm takes. However, there is no place for students to learn and actively practice figuring out the steps each algorithm takes. This web app was created to provide the students with a new means of memorizing, visualizing, and comprehending what each algorithm does.
Like other games, the Sorting Algorithm App was created to be intuitive and easy to use. Since this is a game that is not progression-based, the priority was set on decreasing the number of tasks users must perform before engaging in the game. This app was aimed to provide multiple game modes and algorithms to make the game more interesting and engaging. This game has two game modes: click and drop. With the help of an HTML element swapping tool and a physics engine tool, the two modes were created to support Max Heap Sort, Bubble Sort, Selection Sort, and Insertion Sort.
Methods and Materials
Materials:
Node.js
Express.js
Javascript
Matter.js
Draggable.js
Bootstrap
Sorting algorithms added to the program:
Selection Sort
Insertion Sort
Bubble Sort
Max Heap Sort
Code Procedure and User Instructions:
The Code itself is archived and available in:
User enters the webapp by going to the link csalgs.herokuapp.com
The server side code receives the get request and sends back a render request for home.ejs. Both the bootstrap css and js cdn files are loaded. The user is able to see the webapp, the input fields for the number of input for the game, the game type and the algorithm type. The go button changes the HREF value to the game types: /drop or /click. Regardless of game mode, the game_exports.js file is imported, storing the information of implementable sorting algorithms such as an array for the steps towards the sorted state and the number of steps the user has to take to properly sort the array. The elements of the document object were designed with Bootstrap 4.
Route / Drop
User is routed to the /drop route and the HTML, javascript, CSS files are loaded.
The drop option brings the user to a page where 2d shapes exist in a <canvas> element created by the matter.js physics engine. When the start function is called, a random array of numbers is created by game_exports so that the total number of solution steps the user must take is greater than 5. With the physics engine, the Engine, Renderer, Runner, and various event handlers such as MouseConstraint and Events variables are instantiated and incorporated into the World object. The circles on top of the page are ordered according to the random array and after the page is loaded, the native function requestAnimationFrame is called for the render function along with all the force calculations, starting the animation by having the circles fall down due to a gravitational force.
The user clicks and drags the ball so that the ball can eventually touch another ball.
When two balls touch one another, the switch is checked with the solution steps array. For example, if the current array - the position of the balls - is [1,4,3,2,6,5] and the next step in the solution steps array is changing the 3 and the 4, the code checks if the array formed after the switch [1,3,4,2,6,5] is valid with the checkSolution function available in the object created with game_exports. If so, the two circles switch places and shows a green “success” <div> and if not, the two circles stay in their original spots and a red “failure” <div> will show. This success and failure div is changed into a button to restart the game after the user successfully solves the algorithm.
Route /click
User is routed to /click
The click option uses the swappable.js tool which allows the movement of divs within a container. This option also has the ability to mimic the action of switching two divs’ positions and insert a div in a certain position in the container. The swappable.js tool allows the user to do this using drag and drop methods, taking care of all the click and drop events. Unlike /drop, the click game mode allows the user to play with the insertion sort algorithm.
The user clicks a div, drags it to another position and drops it
The previous array of the positions of numbers is stored locally. The swappable.js tool allows the div to snap into the position nearest to the dropped spot, pushing back all over divs for the “draggable” (insertion) method and swapping the div with the one in the original position for the “swappable” (swapping) method. After the action has been resolved, dragEndFunc is called where the order of the divs’ numbers are stored in an array and put into the checkSolution function. If the checkSolution function returns true, a div shows a “correct” message in green. However, if it returns false, a div shows an “incorrect” message in red and the user action is undone by replacing the pre-existing divs in the container by new ones created based on the previous array of positions stored locally before the action.
Data
Figure 1. Overall View of the Application’s Main Page
Figure 2. View of the Sort “Click” Game
Figure 2 Notes: A green(success) or red(failure) div can be seen after moving a number to another spot.
Figure 3 View of the Sort “Drop” Game
Figure 3 Notes: Here, scenes are created by matter.js and put on the document <canvas> element. The individual circles are affected by a gravitational force and are draggable within the space provided. A green(success) or red(failure) div can be seen after moving a number to another spot.
Conclusion
The Sorting Algorithm Game can be used by students and people who want to memorize how the algorithm works and those who just want to have fun. The simpler approach omitting user sign-in and sign-up for this app was chosen because it added an unnecessary step for users to play the games. Another reason why that was omitted was because the information useful to users such as the progression of the amount it took for them to sort the numbers can be easily remembered and not many would realistically prefer signing up to practice sorting algorithms.
While this app works very well and gives students a simple way to practice sorting algorithms, many additions and improvements can be made. One improvement that I have started working on is the addition of a multiplayer mode where students can compete on who sorts fastest and has least mistakes. For this to be implemented, there must be a system for grouping like those of many .io games. Another improvement would be the addition of more sorting algorithms, not just the simple four. If an adequate way to represent the steps of a recursive function is found, recursive sorting algorithms such as Mergesort and Quicksort can be put in the game. In addition to more algorithms, another possible improvement would be the inclusion of other game modes. This app was created so that it would be easy to create more game modes; because there is a single importable algorithm game tester, people who desire to further this project without adding sorting algorithm logic to their project.
Works Cited
Sehgal, Karuna. “An Introduction to Bubble Sort.” Medium, Karuna Sehgal, 12 Feb. 2018, medium.com/karuna-sehgal/an-introduction-to-bubble-sort-d85273acfcd8.
Sehgal, Karuna. “An Introduction to Insertion Sort.” Medium, Karuna Sehgal, 17 Jan. 2018, medium.com/karuna-sehgal/an-introduction-to-insertion-sort-16b97619697.
Sehgal, Karuna. “An Introduction to Selection Sort.” Medium, Karuna Sehgal, 15 Jan. 2018, medium.com/karuna-sehgal/an-introduction-to-selection-sort-f27ae31317dc.
Joshi, Vaidehi. “Heapify All The Things With Heap Sort.” Medium, Basecs, 19 July 2017, medium.com/basecs/heapify-all-the-things-with-heap-sort-55ee1c93af82.