Techniques for Algorithm Animation Using JavaScript

• Download source - 1 Kb

Introduction

The purpose of this post is to present some basic techniques for algorithm animation using JavaScript. The first of these techniques was used by the author in some previous CodeProject articles for Tower-of-Hanoi and Quicksort.

In this article, we present a second technique and use it for animating Selection Sort and Insertion Sort algorithms. The code can be run from here.

Both techniques can be used for animating recursive algorithms. In particular, we show animation for recursive versions of Selection Sort and Euclid's greatest common divisor (GCD) algorithm. The latter example can be run from here.

Algorithm Animation

The goal of algorithm animation is to show the viewer (learner) a live trace of the algorithm execution, showing data modifications and various intermediate results. However, a useful animation is one that depicts this information in a vivid visual form that assists the viewer in understanding how the algorithm works.

Algorithm animation is usually utilized by computer science educators as a teaching aid for their students, primarily for courses on data structures and algorithms.

In the early years of the web (1995-2003), Java applets were a popular option for implementing algorithm animation. To run applets, the web browser will normally utilize a plug-in that loads Java runtime. As they became more concerned with security risks, the majority of web users have become weary of using plug-ins including applets. JavaScript, on the other hand, is run directly by the browser inside a sand-boxed environment and with limited functionality so as to minimize security risks. With the advancement of client-side web technologies (HTML5 Canvas, SVG, CSS3, DOM, etc.), JavaScript has become a viable option for implementing algorithm animation.

Techniques for Algorithm Animation

A plausible approach for algorithm animation is to insert code consisting of two function calls "ActivateAnimation(); Delay(T);" at some appropriate points within the program code of the algorithm to be animated. The call Delay(T) is meant to introduce a delay for a time duration T, while the animation is being played out. However, there is a big problem. JavaScript lacks a "real" delay or sleep mechanism. If we are to implement the delay by a spin-loop, it would bring things to a stand-still because the whole of JavaScript code executes on one thread.

To address preceding problem, we have come up with the following techniques (with a coined name for each) for algorithm animation.

Technique 1 (Stack Technique): Set aside a stack. Modify the program code of the algorithm to be animated with additional code to push into the stack the values for various parameters needed for animation. Run the modified algorithm til completion. Then process the stack and utilize JavaScript setInterval() function combined with some visual elements to show the algorithm progress.

This technique was successfully used for Tower-of-Hanoi and Quicksort as discussed in the relevant articles by the author.

Technique 2 (Tick Technique): View the time during algorithm execution as ticking (for this, we use a global variable Tick which is incremented every time the algorithm reaches some predefined state) and then abort execution when Tick reaches some predefined value maintained by another variable TargetTick. For example, if we are to abort the execution of a function f when it executes 5 loop iterations, we can set TargetTick to 5 and start with Tick= 0 and increment Tick after every iteration. Interestingly, if at his stage, we increment TargetTick, reset Tick to 0 and re-execute the function f, then the function will execute past the previous state and completes 6 iterations. This is precisely the idea behind the animation for Insertion Sort and Selection Sort algorithms given here. The process is generic and thus can be applied to other algorithms. The earlier pattern "ActivateAnimation(); Delay(T);" can now be coded as, "if (UpdateTick()) { ActivateAnimation(); return; }". Note the use of "return" to abort algorithm's execution. Execution will resume (from the very beginning of execution history) after a time duration that is already set in a call to setInterval().

The function UpdateTick() increments Tick and returns true if Tick is equal to TargetTick. In our code for the Selection Sort and Insertion Sort algorithms, the preceding line is inserted in the innermost loop and is coded as, "if (UpdateTick()) { PrintArray(A, ...); return; }".

Note: The function ActivateAnimation() is simply named PrintArray(). The function PrintArray() renders the array as an HTML list with varied styling applied to certain items of the list.

Thus, the pattern for the overall animation process is as follows.

1. Set TragetTick = 1.
2. Execute the procedure to be animated from start (Tick = 0) till Tick = TragetTick.
3. Increment TargetTick.

Steps 2 and 3 are to be executed repeatedly. Thus, they are enclosed inside a JavaScript function that is executed repeatedly using a call to setInterval().

More specifically, we have these functions named as AnimateSelectionSort() for Selection Sort and AnimateInsertionSort() for Insertion Sort, and are shown next.

function AnimateSelectionSort()  
{  // This function is executed repeatedly via SetInterval()
   // Note: TargetTick is incremented with every call to this function 
   
   Tick=0;
   SelectionSort(A); 
   TargetTick++;   
}

function AnimateInsertionSort()
{ // This function is executed repeatedly via SetInterval()  
  // Note: TargetTick is incremented with every call to this function 
  
  B = A.slice(); // Start from an original copy of A   
  Tick=0; 
  InsertionSort(B); 
  TargetTick++;   
}

The preceding functions are algorithm independent, except, of course, for the line that refers to the function associated with the actual algorithm being animated. Each of the preceding functions is activated using setInterval() function. The interval time determines the animation speed, the smaller the interval the faster the animation. Every time the function is activated, it is in fact executed from the very beginning of execution history. Therefore, it is safer (and actually makes sense) to use the original (unmodified) input to the algorithm. This is why we have in the function AnimateInsertionSort(), the call to InsertionSort() uses a copy of the original input array. We have found that this is not needed for our SelectionSort() function. The program code for SeectionSort() function is given in the next section. The program code for InsertionSort() can be found in the article download HTML file.

Using the Tick Technique for Recursive Algorithms

The reader might wonder whether the Tick technique will work with recursive algorithms. The answer is affirmative. We show two examples.

As a first example, consider SelectionSort_Rec() function, which is a rewrite (a slight modification) of the function SelectionSort() into a "recursive" version. The following program code listing contrasts these functions. The lines (in bold) are for the code to enable animation.

function SelectionSort(A) 
{   
   for (var i = 0; i < A.length-1; i++) 
   {  var min_pos = i;
      var min = A[i];
      for(var j = i; j < A.length; j++)
      {   if (A[j] < min )
          {  min_pos= j; min =A[j]; }

          if (UpdateTick()) { PrintArray(A,i,j,min_pos); return; }
      }

      // swap A[i] with A[min_pos]
      var t = A[i]; A[i] = A[min_pos]; A[min_pos] = t;
   }

   // (i > A.length) last call to Printarray() to show array after final swap
   PrintArray(A,i+1,-1,-1); 
  EndAnimate(); 
}

function SelectionSort_Rec(A,i) 
{   
    if (i >= A.length-1)
    {  // (i > A.length) last call to Printarray() to show array after final swap
       PrintArray(A,i+1,-1,-1); 
       EndAnimate(); 
       return;
    }
 
    var min_pos=i ;
    var min = A[i];
    for(var j = i; j < A.length; j++)
    {  if (A[j] < min )
       {  min_pos= j; min =A[j]; }

       if (UpdateTick()) { PrintArray(A,i,j,min_pos); return; }
    }

    // swap A[i] with A[min_pos]
    var t = A[i]; A[i] = A[min_pos]; A[min_pos] = t; 

    SelectionSort_Rec(A,i+1); // Recursive call
}

function EndAnimate()
{  clearInterval(Timer1);  } 
 
function UpdateTick()
{  Tick++;
   return (Tick == TargetTick);
}

function PrintArray(A, prevleft, prevright)
{ // This function renders the array A as an HTML list 
  // Program code is omitted for brevity  
}

For our second example, we consider the animation of Euclid's GCD algorithm. The animation simply shows the recursion tree with one node for every recursive call entered or exited, as shown in the preceding figure. The tree is drawn gradually reflecting the algorithm's progress of execution.

Some of the program code for the GCD animation is shown in the following listing. The lines (in bold) are for the code to enable animation.

function gcd(a,b)
{ // last param of Print() is either -1 to mean gcd() is entered
  // or positive (the gcd value) and also means gcd() is exited

   if (UpdateTick()) 
   { Print(a,b, -1); return; }  
  
   var c = a % b;
   
   if (c==0)
   {   if (UpdateTick())   
       { Print(a,b, b); return; }  

       return b; 
   }
   else 
   {  var k = gcd(b,c);

      if (UpdateTick())   
      { Print(a,b, k); return; }  

      return k;
    }
}

function Print(a,b,c) 
{  // Program code is omitted for brevity  
}

Concluding Remarks

The program code was tested in latest versions of popular browsers. It works properly in latest versions of IE (version 11), Chrome (version 30), and Firefox (version 24).