14,984,043 members
Articles / Web Development
Article
Posted 29 May 2014

24.3K views
12 bookmarked

Quicksort Animation using JavaScript

Rate me:
The article describes a technique for animating Quicksort algorithm using JavaScript

Introduction

The purpose of this post is to present a possible animation of Quicksort algorithm using JavaScript. Quicksort is a practical and fast sorting algorithm. It is a fundamental topic in the standard algorithm course in computer science. The algorithm for Quicksort serves as a good example of the divide-and-conquer algorithm-design technique; a technique for which the resulting algorithm can be compactly and elegantly expressed using recursion. As an aid to understanding the algorithm, an educator might show a trace of the algorithm's execution on some specific input. The trace normally shows the content of the input array and other key parameters at various stages during execution. This is essentially what our JavaScript code does but in a vivid way.

The animated Quicksort algorithm can be run from here.

The interface provides one of two views (Display list-box). In the "Shrunk" view, the array is shown for every call of the algorithm with the values for the lo,hi, and mid parameters shown to the left. The line-display for the current array dynamically changes with every swap. In the "Expanded" view, the array is shown on a separate line for every swap of elements with the swapped elements highlighted using a distinct color. In both views, the elements from lo to hi are shown with a gray background, while other elements will have a white background. The pivot is identified with red foreground color.

The approach used for animation uses the same technique presented by the author in the Tower-of-Hanoi article. As noted by the author, placing the `setInterval()` calls directly within the procedure to be animated is a recipe for chaos. An effective alternative is to run the normal unanimated procedure until completion whilst using a stack to save the parameters of interest. Then process the stack and utilize JavaScript setInterval() function combined with some visual elements to show the algorithm progress.

How does Quicksort work?

The recursive algorithm for Quicksort can be expressed by the following `Quicksort(A, lo, hi)` JavaScript function:

JavaScript
```function Quicksort(A, lo, hi)
{  if (lo < hi)
{  var mid = Partition(A,lo,hi);
Quicksort(A,lo,mid-1);
Quicksort(A,mid+1,hi);
}
} ```

The input to the function is an array A of the items to be sorted. The lo and hi parameters denote, respectively, the lowest index and highest index of some unsorted section within the array. For the initial call of the above function, the lo and hi parameters are respectively set (by caller) to the first (leftmost) and last (rightmost) indices of the array.

As illustrated by the preceding figure, Quicksort uses a divide-and-conquer strategy, dividing the input array into two parts (sections) and sorting each part recursively. Quicksort uses an auxiliary procedure to perform in-place partitioning of its input (in-place means without using an additional working array). The Partition procedure works as follow:

it picks an element P and arranges the elements so that elements ≤ P are moved to the left side of the sequence and the elements > P are moved to the right side. The element P used for partitioning is referred to as the pivot element. The pivot can be any of the elements in the input sequence to be partitioned; however, quite often, the first (leftmost) element is chosen as the pivot.
JavaScript
```function Partition(A, lo, hi)
{// Input: An integer array A[lo..hi]
// Output: The array A arranged as: elements <= pivot, pivot, elements > pivot
// Return the final position of pivot
// The pivot is A[lo] but it can be any of the elements A[lo], ..., A[hi];
// If pivot is other than A[lo] then (at the start) swap it with A[lo]

paramStack.push([-lo,hi]); // push lo and hi

var pivot = A[lo];
var left = lo+1;
var right = hi;
while (left <= right)
{  while ((left <= right) && (A[left] <= pivot)) left++;
while ((left <= right) && (A[right] > pivot)) right--;
if (left < right)
{  // save left and right parameters to paramStack array
paramStack.push([left,right]);
var t = A[left]; A[left] = A[right]; A[right] = t; left++; right--;
}
}

// Final swap: swap pivot with A[right] and return right (final pivot location)
A[lo] = A[right]; A[right] = pivot;
paramStack.push([lo,right]); // push lo and right
return right;
}```

One simple algorithm for partitioning the input array is given by the preceding `Partition()` function.

Note: The function includes modifications in three places (the lines in bold) that use `paramStack.push()` to save the lo and hi values as well as the locations of the array elements being swapped.

This uses two pointers (left and right) that are, respectively, set to the start and end of the array to be partitioned. The left pointer moves toward the right, skipping elements ≤ pivot, whereas the right pointer moves toward the left, skipping elements > pivot, but where the left and right pointers stop and left < right, the corresponding elements are swapped. The process ends when the left and right pointers meet or pass each other. Then a final swap involving the pivot element and the element pointed to by the right pointer is executed to put the pivot into its proper sorted location.

Animation of Quicksort

As shown by the preceding figure, our program code for the animated Quicksort consists of six functions:

`ExecuteQS()`, `Quicksort()`, `Partition()`, `ProcessStack()`, `PrintArray()`, `AnimateArrow()`.

The above figure shows the relationship among these functions. The functions Quicksort() and Partition() are as given previuosly. The following shows partial code for the other functions.

JavaScript
```var A;  // The input array for Quicksort
var paramStack; // A global array used as a stack

function ExecuteQS()
{ // Some initialization code goes here, omitted form brevity
// The array A (global) is the input to Quicksort

paramStack=[]; // paramStack array is global
var B = A.slice(); // Make a duplicate of array A
Quicksort(A,1,A.length-1);

A = B.slice(); // Restore array A
ProcessStack();
}

function ProcessStack()
{  var elem = document.getElementById("arr0");
if (elem) elem.parentNode.removeChild(elem);
elem = document.getElementById("arr1");
if (elem) elem.parentNode.removeChild(elem);

if (paramStack.length==0)
{ PrintArray(A,-1,0); return; }

gelem1 = null; gelem2 = null;
newRow = false;
var param = paramStack.shift(); // Get parameters from paramStack

left = param[0]; right = param[1];

if (left < 0)  // Check if parameters are lo and hi
{  newRow =true;
lo = -left;  hi = right;

prevleft = lo;  // a bug creeps if RHS is lo+1
prevright = hi;

param = paramStack.shift();

left = param[0]; right = param[1];
}

dispLeft = left-prevleft; // no. of cells to move left arraow
dispRight = prevright-right ; // no. of cells to move right arraow

if (left==lo) dispLeft = right - prevleft;

PrintArray(A, prevleft, prevright);

prevright = right; prevleft = left;

// Modify the array; the modified array will be shown the
// next time ProcessStack() (and thus PrintArray) is called
var t = A[left]; A[left] = A[right]; A[right] = t;

if (!Timer1) Timer1 = setInterval(AnimateArrow,Speed); // Start animation
}

function PrintArray(A, prevleft, prevright)
{ // This function renders the array A as an HTML list
// The program code is omitted for brevity
}
function AnimateArrow()
{ // This function is called as a result of
// the call to setInterval() in ProcessSatck()
// The program code is omitted for brevity
}```

Concluding Remarks

In the rendered animation, the left arrow is not allowed to move past the right arrow. This behavior is acceptable, since the data that is saved to the stack are places of swaps and not necessarily all the locations that the left arrow has passed through. The "predefined" example for n=20 shows (first line of output) that the left arrow is not moving because its current location is where the right arrow will end up.

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).

Share

 Instructor / Trainer KFUPM Saudi Arabia

Nasir Darwish is an associate professor with the Department of Information and Computer Science, King Fahd University of Petroleum and Minerals (KFUPM), Saudi Arabia.

Developed some practical tools including COPS (Cooperative Problem Solving), PageGen (a tool for automatic generation of web pages), and an English/Arabic full-text search engine. The latter tools were used for the Global Arabic Encyclopedia and various other multimedia projects.

Recently, developed TilerPro which is a web-based software for construction of symmetric curves and their utilization in the design of aesthetic tiles. For more information, visit Tiler website.

 First Prev Next
 Quicksort Animation using JavaScript Member 1475818528-Feb-20 0:43 Member 14758185 28-Feb-20 0:43
 About Animation Member 1423012013-Apr-19 0:34 Member 14230120 13-Apr-19 0:34
 My vote of 5 Humayun Kabir Mamun5-Nov-15 20:07 Humayun Kabir Mamun 5-Nov-15 20:07