Quicksort procedure for containers (using recursion in AX 2012)

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.

‍