Quicksort procedure for containers (using recursion in AX 2012)

Continue reading

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.

More articles
Explore our blog

What can we do for you?

We'd love to hear about your project. Our team will get back to you within two working days.

Thank you for inquiry, we’ve passed it to our sales department, our representative will reach you back in his earliest convenience.
Oops! Something went wrong while submitting the form.