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:
- Pick an element, called a pivot, from the array.
- 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.
- 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)
// 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);
conGreater += conPeek(_conSort, i);
return (this.conQuickSort(conLess) + pivotId + this.conQuickSort(conGreater));
The steps from above X++ representation of quicksort procedure are:
- Define the variables for left partition, right partition, the pivot, the index and simply a counter for iterating through the partitions.
- Then remove the pivot value from the container.
- 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.
- 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();
FromTime startTime = timeNow();
qsResultCon = quickSort.conQuickSort(qsCon);
for (i = 1; i <= conLen(qsResultCon); i++)
info(strFmt("Total time consumed within this operation is %1", timeConsumed(startTime, timeNow())));
And happy DAXing.
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.