QuickSort-Enabled CArray Template Class


Desktop-as-a-Service Designed for Any Cloud ? Nutanix Frame

Environment: Visual C++ 5.0 & SP3, Windows NT 4.0 & SP5, Unicode, MBCS

This is an updated version - thanks to Donald R. Kichline.


From time to time, I need to sort arrays containing custom data types, structures, or simple data types provided by C++.  Because I use MFC and CArray, I was looking for a nice solution.  Here it is - my CQArray template class that includes a quick sort method.  In the first version I just provided array template with quick sort method implemented.  This is updated version, with function template too.  Good news, this release is faster than first one, and of course, faster than qsort() function.  Second one is, I extended it by QuickSort() function template.

Description of solution

Sorry, I don't describe the quick sort algorithm.  You should be aware that the quick sort algorithm is the fastest sorting algorithm.  It is recursive, and based on partitioning the input array by some element.

In this release is new function template - QuickSort().  This template is also used by CQArray template.  Therefore, now it is possible to sort any array, not just a CArray like array.

I kept it as simple as possible.  With CQArray, you can construct any template class.  After construction, by simply calling QuickSort(), you will sort the array.  The function template QuickSort() works the same way.

Description of CQArray template

CQArray declaration and implementation:

  template <class T, class PT> class CQArray : public CArray <T, PT>
    void QuickSort(BOOL bAscending = TRUE);

  template <class T, class TP> void CQArray<T,TP>::QuickSort(BOOL bAscending/* = TRUE*/)
    if (GetSize() > 1) {

Above you can see whole CQArray template.  One and only method is QuickSort(), parameter bAscending means sorting ascending (if TRUE), or descending.  Note, this method calls QuickSort() function.

Description of function template QuickSort

Declaration of QuickSort() function:

  template <class T> BOOL QuickSort(T *pArr, int iSize, BOOL bAscending = TRUE);

Implementation is quite longer, please see to sources.  First parameter is address of array to sort.  Second one is size of this array.  Last one has same meaning like CQArray::QuickSort() parameter.  Function returns TRUE if success, otherwise it returns FALSE.  However, only one error can occur - bad parameters.


Usage of CQArray is similar to a CArray:

  CQArray <int, int &> intArr;
  // do some stuff to fill array

Usage of QuickSort() function:

  int data[100];

Note, if you want to sort a custom type, you'll need to overload the operators '<' and '>'.

Demo project

I provide simple demo project.  You can see usage of template class and function and compare performance of QuickSort() function with qsort() function.

qarray.jpg (19721 bytes)

You can set array size, type of elements in array and direction of sorted array.  My 'user defined type' is simple structure.

Comparision with qsort

As you can see on previous picture, in demo program you can sort array in three ways.  First one is with CQArray template, second one QuickSort() function template and last one is qsort() function.  Time bellow is in seconds.  My templates are faster than qsort() function.  It is not every time seven times faster, sometimes it is more or less.  It is based on array size, a larger array produces a better ratio.


Date Updated: 12 June, 1999



  • How can i return CArray object from Function

    Posted by renugopal on 06/20/2005 09:33am

    I want to pass and return CArray object with Function how can i implement this Thanks -Renugopal

  • more programming example

    Posted by Legacy on 02/23/2004 08:00am

    Originally posted by: Azlie.Syawal

    why don't you put more example of sorting program that simple to learn and understand.All include with notes..
    hope you will concern my opinion.bye

  • Qsort in most cases IS the fastest algorithm

    Posted by Legacy on 08/12/2002 07:00am

    Originally posted by: Dominic

    On average qsort is O(N log N) , infact with a 99:1 split mathematically it is still O(N log N) and because it sorts in place it is often the fastest algorithm. Heap sort may be guarenteed O(N log N), but there is a large overhead associated with maintaining the heap and hence it is often slower than qsort with random pivot selection.

  • Is there an error in the algorithm ??

    Posted by Legacy on 08/02/2002 07:00am

    Originally posted by: Marc

    I'm using the template and until now I thougt, that it is a great help. But now I found out, that the algorithm not always finds the smalles element in a list, if I sort it in ascending order. It seems to be, that the algorithm sets the second smallest object as the smallest. Does anybody made similar experiences ??

  • Using QSort with class arguments

    Posted by Legacy on 07/31/2002 07:00am

    Originally posted by: Alex H

    Is it possible to somehow use this sort function with a CArray <MyClass, MyClass> MyClassArray where MyClass contains an int to sort on. Of course MyClass also contains other variables that must remain with the int in MyClass.



  • EXACTLY what i was looking for!

    Posted by Legacy on 05/29/2002 07:00am

    Originally posted by: John G

    Not often you find exactly what you were looking for on the net. your search template method was exactly what i was looking for. i modified it to not modify the passed in array but modify an indexes array instead, but it works perfect!

  • I wrote a sorting program that beats everything Ive seen

    Posted by Legacy on 02/23/2002 08:00am

    Originally posted by: Jack Calhoun

    I can't go into too much detail, because I havent written a paper to take credit. I just wrote it this morning.

    Results averaged over 100 executions each:

    Sorting 100 random Numbers between 1 and 100,000
    avg = 168 comparisons

    Sorting 250 random Numbers between 1 and 100,000
    avg = 418 comparisons

    Sorting 500 random Numbers between 1 and 100,000
    avg = 834 comparisons

    Sorting 1000 random numbers between 1 and 100,000
    avg = 1,675 comparisons

    Sorting 2000 random numbers between 1 and 100,000
    avg = 3,331 comparisons

    Sorting 4000 random numbers between 1 and 100,000
    avg = 6,676 comparisons

    Sorting 8000 random numbers between 1 and 100,000
    avg = 13,102 comparisons

  • QuickSort is NOT the fastest sorting algoritm

    Posted by Legacy on 05/03/2000 07:00am

    Originally posted by: Robert Vogt IV

    QuickSort is not the fastest sorting algorithm. QuickSort should also never be used in arrays with more than 256 elements.

    The two fastest sorting algorithms, for both large and small arrays, are Heap Sort and Merge Sort. (Heap Sort is guaranteed NlogN order, while QuickSort can become quadratic.)

    Finally, QuickSort was one of the first sorting algorithms with much of an advantage over Bubble Sort. However, newer sorting mechanisms have made it practically useless for modern-day sorting (millions or billions of elements).

    -Robert Vogt IV

  • New e-mail

    Posted by Legacy on 03/11/2000 08:00am

    Originally posted by: Martin Ziacek

    My old e-mail is no longer valid. New: Martin.Ziacek@pobox.sk

  • CListBox is faster

    Posted by Legacy on 01/25/2000 08:00am

    Originally posted by: CMan

    please send me the advantages of heep sort over qsort in terms of time and swaps saving
    my email is

  • Loading, Please Wait ...

  • You must have javascript enabled in order to post comments.

Leave a Comment
  • Your email address will not be published. All fields are required.

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date