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)
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:
- 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();
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.
