**THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED**

*On 07/05/2009 at 21:11, ***xxxxxxxx** wrote:

Hi Jon,

What a timely thread for me...just looked into the same problem earlier this week. I'll post our efforts. We translated a version of the wikipedia quicksort from the very useful C code at the bottom of the page:

http://en.wikipedia.org/wiki/Quicksort

into Coffee and will try to post here. Our amateur's modification is capable of sorting arrays of multiple dimension by any single user-selected dimension. I hope someone else may find use for it.... It would be great if someone wanted to add the ability to sort within the dimensions as well e.g., when there are redundancies in the current sorted dimension. Might also be nice to have a stablesort version.

Thanks,

Graham

http://www.grahamj.com

> ` \> // Quicksort the array... modified from C code posted at http://en.wikipedia.org/wiki/Quicksort \> // translated May/7/2009 by Graham & Mostafa \> // This functions ~10x faster than simple sorting on my test polyhedron with ~5500 polygons \> // reducing sort time from 0.62s to 0.068sec on a 2x 3GHz Dual-Core Intel Xenon running C4D v11.027 \> f_quicksort(pArray, pDimension, pLeft, pRight, pArrayWidth) \> { \> if(pLeft >= pRight) \> return; \> var index = f_partition(pArray, pDimension, pLeft, pRight, pArrayWidth); \> f_quicksort(pArray, pDimension, pLeft, index - 1, pArrayWidth); \> f_quicksort(pArray, pDimension, index + 1, pRight, pArrayWidth); \> } \> \> // Partition the pArray into two halves and return the \> // index about which the pArray is f_partitioned \> f_partition(pArray, pDimension, pLeft, pRight, pArrayWidth) \> { \> // Makes the leftmost element a good pivot, \> // specifically the median of medians \> f_find_median_of_medians(pArray, pDimension, pLeft, pRight, pArrayWidth); \> var pivotIndex = pLeft, pivotValue = pArray[pivotIndex][pDimension], index = pLeft, i; \> f_swap(pArray, pDimension, pivotIndex, pRight, pArrayWidth); \> for(i = pLeft; i < pRight; i++) \> { \> if(pArray[I][pDimension] < pivotValue) \> { \> f_swap(pArray, pDimension, i, index, pArrayWidth); \> index += 1; \> } \> } \> f_swap(pArray, pDimension, pRight, index, pArrayWidth); \> \> return index; \> } \> \> // Computes the median of each group of 5 elements and stores \> // it as the first element of the group. Recursively does this \> // till there is only one group and hence only one Median \> f_find_median_of_medians(pArray, pDimension, pLeft, pRight, pArrayWidth) \> { \> if(pLeft == pRight) \> return pArray[pLeft][pDimension]; \> var i, pShift = 1; \> while(pShift <= (pRight - pLeft)) \> { \> for(i = pLeft; i <= pRight; i+=pShift\*5) \> { \> var endIndex = (i + pShift\*5 - 1 < pRight) ? i + pShift\*5 - 1 : pRight; \> var medianIndex = f_find_median_index(pArray, pDimension, i, endIndex, pShift, pArrayWidth); \> \> f_swap(pArray, pDimension, i, medianIndex, pArrayWidth); \> } \> pShift \*= 5; \> } \> \> return pArray[pLeft][pDimension]; \> } \> \> // Find the index of the Median of the elements \> // of pArray that occur at every "pShift" positions. \> f_find_median_index(pArray, pDimension, pLeft, pRight, pShift, pArrayWidth) \> { \> var i, groups = (pRight - pLeft)/pShift + 1, k = pLeft + groups/2\*pShift; \> for(i = pLeft; i <= k; i+= pShift) \> { \> var minIndex = i; \> var minValue = pArray[minIndex][pDimension]; \> var j; \> for(j = i; j <= pRight; j+=pShift) \> if(pArray[j][pDimension] < minValue) \> { \> minIndex = j; \> minValue = pArray[minIndex][pDimension]; \> } \> f_swap(pArray, pDimension, i, minIndex, pArrayWidth); \> } \> return k; \> } \> \> // Swap integer values by pArray indexes \> f_swap(pArray, pDimension, pA, pB, pArrayWidth) \> // DO NOT DELETE THE CODE BELOW!!! You may find it useful \> // The k looped code below is generic to sort an arrray of any dimension = pArrayWidth, \> // but the loopless version worked ~11% faster on my ~5500 polygon \> // test critter to sort a 2D array by its second dimension for example. \> /\* \> { \> var tmp = pArray[pA][pDimension]; \> var tmp0 = pArray[pA][0]; \> pArray[pA][pDimension] = pArray[pB][pDimension]; \> pArray[pB][pDimension] = tmp; \> pArray[pA][0] = pArray[pB][0]; \> pArray[pB][0] = tmp0; \> }\*/ \> { \> var k; \> var vTemp; \> for (k = 0; k < pArrayWidth; k++) \> { \> vTemp = pArray[pA][k]; \> pArray[pA][k] = pArray[pB][k]; \> pArray[pB][k] = vTemp; \> } \> } \> `