Tutorial

Quicksort procedure for containers (using recursion in AX 2012)

Quicksort procedure for containers (using recursion in AX 2012)
Published in
April 2015

Quicksort is efficient sorting algorithm which is useful for sorting any data structures that have some sort of key. In this article I’ll show how to create basic quicksort algorithm in X++ for containers containing numbers.

And in some of the next articles I’ll show you the real world usage of this algorithm for Microsoft Dynamics AX containers. The quicksort algorithm basic steps are:

  1. Pick an element, called a pivot, from the array.
  2. Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

First create a class and a new method in it with the following code:

public container conQuickSort(container  _conSort)

{

   container   conLess = conNull(), conGreater = conNull();

   int         pivotId, pivotIdx, i;

   // Check for null array

   if (conLen(_conSort) <= 1)

       return _conSort;

   // Select pivot value and remove it from the container

   pivotIdx    = conLen(_conSort)/2 + ((conLen(_conSort)/2) mod 2);

   pivotId     = conPeek(_conSort, pivotIdx - 1);

   _conSort    = conDel(_conSort, pivotIdx - 1, 1);

   // Partinioning of the main array

   for (i = 1; i <= conLen(_conSort); i++)

   {

       if (conPeek(_conSort, i) <= pivotId)

       {

           conLess     += conPeek(_conSort, i);

       }

       else

       {

           conGreater  += conPeek(_conSort, i);

       }

   }

   //recursive call

   return (this.conQuickSort(conLess) + pivotId + this.conQuickSort(conGreater));

}

The steps from above X++ representation of quicksort procedure are:

  1. Define the variables for left partition, right partition, the pivot, the index and simply a counter for iterating through the partitions.
  2. Then remove the pivot value from the container.
  3. Rearrange the main array i.e. moving the values less than pivot value in left partition and the ones greater than the pivot value in the right partition.
  4. Creating the result container with recursive call to the same function with passing the two containers as arguments.

And then in order to test the quicksort method just write the following job that will use the quicksort method, print the result and calculate the consumed time, so you can play with different values in the container and see the execution times:

static void quicksortTest(Args _args)

{

   container   qsResultCon, qsCon = [3, 2, 1, 6, 4, 5];

   Class3  quickSort = new Class3();

   Integer i;

   FromTime startTime = timeNow();

   qsResultCon = quickSort.conQuickSort(qsCon);

   setPrefix("Sorted values");

   for (i = 1; i <= conLen(qsResultCon); i++)

   {

       info(int2str(conPeek(qsResultCon, i)));

   }

   info(strFmt("Total time consumed within this operation is %1", timeConsumed(startTime, timeNow())));

}

And happy DAXing.

Written by
Viktor Ristkovski

Microsoft Dynamics developer since 2009 (starting from Dynamics AX 2009) with experience in multiple Dynamics implementations across Europe and in almost any technical area of Microsoft Dynamics. Comes from Skopje, Macedonia, Graduated at Technical University in Varna, Bulgaria as Computer Science Engineer. Always supported by his lovely wife and daughter.