How to use the quick-sort function to sort MFC CArray-derived classes on the MFC and Visual C++ run-time library (216858)

MORE INFORMATION

The Visual C++ run-time library (MSVCRT) implements the quick-sort function, qsort, as follows:

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );
				

The following example shows you how to use this function to sort an MFC CArray class. Although the following example uses a CString array, you can easily customize for other MFC CArray-derived classes, such as CByteArray, CDWordArray, CObArray, CPtrArray, CUintArray, and CWordArray.

Steps to implement sorting

1. Derive your array data class from one of the CArray-derived classes. In our example, we use CStringArray as the base class for our class. The following is the declaration in the header file:

   class CSortableStringArray : public CStringArray
   {
   public:
   protected:
   };
   						

2. To the public section of your class add the following function:

   void Sort(STRINGCOMPAREFN pfnCompare = Compare);
   						

3. To the protected section of your class add the following static function:

   static int __cdecl Compare(const CString * pstr1, const CString * pstr2);
   						

4. Now add the following two type defs above the declaration of your class. These typedefs later help us in passing pointers of the two functions that we declared in steps 2 and 3 to the Visual C++ run-time's qsort function:

   typedef int (__cdecl *GENERICCOMPAREFN)(const void * elem1, const void * elem2);
   typedef int (__cdecl *STRINGCOMPAREFN)(const CString * elem1, const CString * elem2);
   						

5. In your .cpp file, implement the two functions that you declared earlier:

   // 
   // SortableStringArray.cpp
   // 
   
   int CSortableStringArray::Compare(const CString * pstr1, const CString * pstr2)
   {
   	ASSERT(pstr1);
   	ASSERT(pstr2);
   	return pstr1->Compare(*pstr2);
   }
   
   void CSortableStringArray::Sort(STRINGCOMPAREFN pfnCompare /*= CSortedStringArray::Compare */)
   {
   	CString * prgstr = GetData();
   	qsort(prgstr,GetSize(),sizeof(CString),(GENERICCOMPAREFN)pfnCompare);
   }
   						

That is it. Now let's look at the contents of the entire file:

// 
// SortableStringArray.h
// 

typedef int (__cdecl *GENERICCOMPAREFN)(const void * elem1, const void * elem2);
typedef int (__cdecl *STRINGCOMPAREFN)(const CString * elem1, const CString * elem2);

class CSortableStringArray : public CStringArray
{
public:
	void Sort(STRINGCOMPAREFN pfnCompare = Compare);

protected:
	static int __cdecl Compare(const CString * pstr1, const CString * pstr2);
};

// 
// SortableStringArray.cpp
// 

#include "SortableStringArray.h"

int CSortableStringArray::Compare(const CString * pstr1, const CString * pstr2)
{
	ASSERT(pstr1);
	ASSERT(pstr2);
	return pstr1->Compare(*pstr2);
}

void CSortableStringArray::Sort(STRINGCOMPAREFN pfnCompare /*= CSortedStringArray::Compare */)
{
	CString * prgstr = GetData();
	qsort(prgstr,GetSize(),sizeof(CString),(GENERICCOMPAREFN)pfnCompare);
}
				

To use the array in your code, just declare it and call the Sort() function. The following example uses this array:

	srand( (unsigned)time( NULL ) ); // Generate seed for rand().
	CSortableStringArray arr;
	CString str;
	for (int i=0; i< 1000;i++)
	{
		str.Format("%6d", rand());// Get a random number string.		
		arr.Add(str);
		TRACE("%s\n", (LPCTSTR)str);
	}
	long ltim=GetTickCount();
	arr.Sort();
	for (i=0; i< 1000;i++)
	{
		TRACE("%s\n", (LPCTSTR)arr[i]);
	}

	TRACE("Time took= %li\n", GetTickCount()-ltim);
				

Note To implement a CArray type other than CString, just derive your class from the other array types and modify the Sort() and the Compare() functions accordingly.

Note Quick Sort is a more efficient mechanism of sorting than the bubble sort used in the Microsoft Knowledge Base article, "How to Sort a CStringArray in MFC" (Q120961)