Project ListMS - algorithms-in-action/algorithms-in-action.github.io GitHub Wiki

Project 3: Linked list merge sort - more details/updates

Currently AIA has algorithm animations that visualise arrays, various forms of trees and graphs but none that visualise linked lists. This project will add linked list visualisation to AIA, initially using a version of merge sort. There should also be consideration of how the code could be used or adapted to other linked list algorithms (some of which may also be completed in this project).

Preferred visualisation of linked lists

Linked lists are best represented by either some symbol that represents the empty list or an arrow that points to a box that is divided into two parts (or two boxes that are joined), representing a list cell. The first part/box will contain a list element (the head of the list) and the second will contain the empty list symbol or an arrow pointing to the next list cell (the tail of the list). AIA has a module that implements graphs, including various forms of trees, and this has similar visual elements. Extending it to support lists seems like the best solution.

The main files of interest for supporting lists are in the src/components/DataStructures/Graph/ directory. Within this NAryTreeTracer/ and NAryTreeRenderer/ are used for 234-trees and two-nodes in 234-trees look very like list nodes so that code may be useful. One difference between the current data structures supported and lists is that we definitely want multiple lists to be supported in a single module (and have pointers between the two lists in the merge operation, for example).

One possible design would be to have an array of lists that includes all the lists displayed. The tail of a list is itself a list, so we would have one list for every pointer to a "cons cell" (as they are traditionally called) plus one for every empty list. Each list could have an optional name (eg, a variable from the pseudocode; the name would be unused for the tail of most lists), a position (x and y coordinates) and a value. The value is either simply the empty list or the list head (a list element), the list tail (a list, which could be represented as an array index) and a position (the position of the cons cell). Note that a non-empty list has two positions: one for the start of the arrow and one for cons cell at the end of the arrow. It may also be necessary/useful to add flags to indicate where the names should appear (eg, left, right, above or below the list).

The API also needs careful design to make the use of the module as simple as possible while retaining flexibility. For example, having code that automatically determines the positions of list cells (eg, left to right layout) given the position of a named list would be very useful. It is hard to determine what may be required in the future, but having primitives that make the mergesort code relatively simple is a good start. You may want to think about how a linked list version of insertion sort could be coded also. The existing code for AVL trees may be a source of ideas (see src/components/DataStructures/Graph/GraphTracer.js), particularly the use of pauseLayout (which is used to stop the automatic tree layout during rotations) and perhaps moveRatio (which is used to change the layout more gradually).

Discussing the design with the clients (particularly Lee) is strongly encouraged. This project has been attempted before, with limited client discussions during the design phase, and limited success. It is probably a more challenging project than it appears at first.

Visualisation in merge sort

Exactly how the algorithm is visualised will be determined in consultaion with the clients, who have some ideas but these may change as prototypes are developed. For example, a key operation in mergesort is merging two sorted lists L and R to form a new list M. The two input lists could each be displayed horizontally, one above the other. All arrows would point to the right. As the merge operation proceeds, the list cells could remain in the same positions but the arrows and labels such as L and R could change (helping illustrate that the algorithm changes pointers but not the data in list cells). Arrows may then point right, up, down or diagonally. At the end of the merge operation the resulting list M could be re-rendered horizontally for clarity, with all arrows pointing to the right again.

Existing merge sort animation for lists

AIA has a prototype of merge sort for lists implemented (it doesn't appear in the menus but can be found from the main page via the search function - search for "list" and it will come up). Some steps of the execution are not animated and these need to be filled in. However, the main job is to change the way lists are visualised. In the prototype, lists are represented using two arrays: one for the data (the head of each list) and another for the "next pointers" (the tail of each list). Thus head[i] together with tail[i] represent the two components of a single list cell. Instead of a pointer to a list cell we use the index of the arrays that represents the next list cell (so the integer i represents a pointer to the list cell described above). Empty lists are represented by "Null". The pseudocode is written so it is independent of the way lists are represented and it should remain unchanged in this project. We just want the dual arrays replaced by arrows and boxes representing pointers and list cells, respectively.