Click here to Skip to main content
11,934,199 members (36,306 online)
Click here to Skip to main content
Add your own
alternative version


11 bookmarked

Quicksort Animation using JavaScript

, 29 May 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
The article describes a technique for animating Quicksort algorithm using JavaScript

JS_Quicksort Image


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:

function Quicksort(A, lo, hi) 
{  if (lo < hi) 
   {  var mid = Partition(A,lo,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.

Quicksort Image

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

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
  A = B.slice(); // Restore array A 

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


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Nasir Darwish
Instructor / Trainer KFUPM
Saudi Arabia 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 TilerPro web site.

You may also be interested in...

Comments and Discussions

GeneralMy vote of 5 Pin
Humayun Kabir Mamun5-Nov-15 21:07
memberHumayun Kabir Mamun5-Nov-15 21:07 
QuestionCannot download Pin
fredatcodeproject6-Jun-14 10:31
memberfredatcodeproject6-Jun-14 10:31 
AnswerRe: Cannot download Pin
Nasir Darwish14-Jun-14 3:52
memberNasir Darwish14-Jun-14 3:52 
GeneralRe: Cannot download Pin
fredatcodeproject16-Jun-14 1:20
memberfredatcodeproject16-Jun-14 1:20 
QuestionExcellent Article Pin
Suchi Banerjee, Pune2-Jun-14 2:46
memberSuchi Banerjee, Pune2-Jun-14 2:46 
AnswerRe: Excellent Article Pin
Nasir Darwish14-Jun-14 3:54
memberNasir Darwish14-Jun-14 3:54 
GeneralRe: Excellent Article Pin
Suchi Banerjee, Pune14-Jun-14 6:34
memberSuchi Banerjee, Pune14-Jun-14 6:34 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.151126.1 | Last Updated 29 May 2014
Article Copyright 2014 by Nasir Darwish
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid