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

Project 5: Other sorting algorithms - more details/updates

AIA has several sorting algorithm animations. Some of these could be enhanced and animations for some some simpler sorting algorithms could be added.

Top-down merge sort is a doubly recursive algorithm and the current animation has a very simple textual visualisation of the stack. Both quicksort and radix exchange sort have similar recursive structure and the AIA animations have graphical stack visualisations. Having similar graphical visualisations for all three algorithms is desirable.

The quicksort animations in AIA were developed first, including a visualisation of the stack (though this has since been simplified) - see src/algorithms/controllers/quickSort_shared.js. In quicksort, the two recursive calls are never on adjacent array segments - there is always a gap between the array segments due to the pivot element. This simplifies visualisation. The radix exchange sort code was based on the quicksort code but the "left" and "right" array segments in recursive calls can be adjacent so use slightly different colors are used so they can be distinguished. It is probably better to have some kind of visual marker rather than a color change. Also, there have been multiple other changes to the radix exchange sort code (unrelated to the stack) but because of the way the code is structured it has become very messy. It may be worth rewriting this code, but this is a very low priority. However, it is definitely worth avoiding this kind of code structure for merge sort. Ultimately the stack visualisation should look very similar in all these algorithms. In a perfect world the bulk of the stack display code would be shared, but the world is far from perfect...

We would also like to see new animations for other sorting algorithms such as insertion sort and selection sort. We have pseudocode for both these algorithms but would like animations. The look of the animations should be guided by the style used in other AIA sorting animations. Additionally, if there are some ways in which algorithmic complexity could be illustrated better to AIA users, that would be of great benefit.

Of these algorithms, insertion sort is the higher priority because it is a better algorithm (it is adaptive and can be very efficient if the array is already almost sorted). Several sorting algorithms are based on swapping two elements in the array, for which there is a primitive in AIA (eg, swapElements in src/components/DataStructures/Array/Array1DTracer.js) that does tweening in the animation. Insertion sort can be coded with swap operations but is better coded by assigning to/from a temporary variable. However, we have prototype code that will allow swapElements (and tweening) to be used by having extra elements in the array, including one for the temporary variable, but changing how the array is displayed (see columnGapAt in src/components/DataStructures/Array/Array1DRenderer/index.js). This should allow a nice animation of insertion sort without too much work.