Implementing multidimensional Quicksort

[Judd]

I have a function that returns a multidimensional VARIANT array of strings of the form:

[0, 0] Item Name String
[0, 1] Class Name String
[0, 2] Description String

In the first dimension this goes from 0 to 3000. I have been attaching to a COleSafeArray to access the strings using the GetElement method.

I'm writing the data to file and I need to sort the array in ascending order of Item Name, making the appropriate reorganisations of the other two dimensions.

I have a quicksort that seems to work well with a one dimensional CStringArray, but can't seem to make it work with my multidimension COleSafeArray.

Any body got any tips or ideas?

[HarryW]

Before you start worrying about it too much, ask yourself if you really need this to be an array. It looks to me like what you really want it a one-dimensional array of structures. If you already have the code to sort a one-dimensional array, I expect the easiest solution would be to use structs instead of 3-element arrays.

[Judd]

I'm re-using OLE automation calls (that (must) return variants internally). I'm trying to avoid re-writing the functions that get my data (since they all exist already).

At the moment I'm just having trouble sorting one dimension in my COleSafeArray, but the damn thing is hard to watch, so I can't tell what is going on!

[Judd]

This assumes the size/arrangement of elements in the variant, but that is fine for me:

void CXMLHandler::QuickSortRecursive(COleSafeArray *pArr, long lo, long hi, long iSortBy, long iDims, BOOL bAscending)
{
	long i, j, k, indexes[2];
	COleVariant vStrTemp;
	CString strStart, strI, strJ, strIK, strJK;

	strI.Empty();
	strJ.Empty();
	strStart.Empty();

	indexes[1] = iSortBy;

	indexes[0] = ((long)((lo+hi) / 2));
	pArr->GetElement(indexes, &vStrTemp);
	strStart = vStrTemp.bstrVal;

	i = hi;
	j = lo;

	do
	{
		indexes[1] = iSortBy;

		indexes[0] = j;
		pArr->GetElement(indexes, &vStrTemp);
		strJ = vStrTemp.bstrVal;

		indexes[0] = i;
		pArr->GetElement(indexes, &vStrTemp);
		strI = vStrTemp.bstrVal;

		if (bAscending) 
		{
			while (strJ < strStart)
			{
				j++;
				indexes[0] = j;
				pArr->GetElement(indexes, &vStrTemp);
				strJ = vStrTemp.bstrVal;
			}
			while (strI > strStart)
			{
				i--;
				indexes[0] = i;
				pArr->GetElement(indexes, &vStrTemp);
				strI = vStrTemp.bstrVal;
			}
		}
		else
		{
			while (strJ > strStart)
			{
				j++;
				indexes[0] = j;
				pArr->GetElement(indexes, &vStrTemp);
				strJ = vStrTemp.bstrVal;
			}
			while (strI < strStart)
			{
				i--;
				indexes[0] = i;
				pArr->GetElement(indexes, &vStrTemp);
				strI = vStrTemp.bstrVal;
			}
		}

		if (i >= j)
		{
			if (i != j)
			{
				indexes[0] = i;
				vStrTemp = strJ;
				pArr->PutElement(indexes, &vStrTemp);

				indexes[0] = j;
				vStrTemp = strI;
				pArr->PutElement(indexes, &vStrTemp);

				for (k = 0; k <= iDims; k++)
				{
					if (k != iSortBy)
					{
						indexes[1] = k;
						
						indexes[0] = i;
						pArr->GetElement(indexes, &vStrTemp);
						strIK = vStrTemp.bstrVal;

						indexes[0] = j;
						pArr->GetElement(indexes, &vStrTemp);
						strJK = vStrTemp.bstrVal;

						vStrTemp = strIK;
						pArr->PutElement(indexes, &vStrTemp);

						indexes[0] = i;
						vStrTemp = strJK;
						pArr->PutElement(indexes, &vStrTemp);
					}

				}
			}
			i--;
			j++;
		}
	} while (j <= i);

	if (lo < i) QuickSortRecursive(pArr, lo, i, iSortBy, iDims, bAscending);
	if (j < hi) QuickSortRecursive(pArr, j, hi, iSortBy, iDims, bAscending);
}