howto: quick sorting using mfc carray-derived classes id: q216858

---

the information in this article applies to:

• microsoft visual c++, 32-bit editions, versions 5.0, 6.0

---

summary

this article shows you how to quick-sort an mfc carray-derived class. the code below depends only on the mfc and visual c++ run-time library.

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.