QuickSort-Enabled CArray Template Class

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

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

Motivation

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>
  {
  public:
    void QuickSort(BOOL bAscending = TRUE);
  };

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

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

Usage of CQArray is similar to a CArray:

  ...
  CQArray <int, int &> intArr;
  ...
  // do some stuff to fill array
  ...
  intArr.QuickSort();
  ...

Usage of QuickSort() function:

  int data[100];
  QuickSort(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.

History

Date Updated: 12 June, 1999



Downloads

Comments

  • How can i return CArray object from Function

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

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

    Reply
  • more programming example

    Posted by Legacy on 02/23/2004 12: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

    Reply
  • Qsort in most cases IS the fastest algorithm

    Posted by Legacy on 08/12/2002 12: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.

    Reply
  • Is there an error in the algorithm ??

    Posted by Legacy on 08/02/2002 12: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 ??

    Reply
  • Using QSort with class arguments

    Posted by Legacy on 07/31/2002 12: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.

    Thanks,

    alexh1@sbcglobal.net

    Reply
  • EXACTLY what i was looking for!

    Posted by Legacy on 05/29/2002 12: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!

    Reply
  • I wrote a sorting program that beats everything Ive seen

    Posted by Legacy on 02/23/2002 12: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

    Reply
  • QuickSort is NOT the fastest sorting algoritm

    Posted by Legacy on 05/03/2000 12: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

    Reply
  • New e-mail

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

    Originally posted by: Martin Ziacek

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

    Reply
  • CListBox is faster

    Posted by Legacy on 01/25/2000 12: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
    andy_dharia@hotmail.com

    Reply
  • Loading, Please Wait ...

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

Top White Papers and Webcasts

  • Live Event Date: October 29, 2014 @ 11:00 a.m. ET / 8:00 a.m. PT Are you interested in building a cognitive application using the power of IBM Watson? Need a platform that provides speed and ease for rapidly deploying this application? Join Chris Madison, Watson Solution Architect, as he walks through the process of building a Watson powered application on IBM Bluemix. Chris will talk about the new Watson Services just released on IBM bluemix, but more importantly he will do a step by step cognitive …

  • Live Event Date: October 29, 2014 @ 1:00 p.m. ET / 10:00 a.m. PT It's well understood how critical version control is for code. However, its importance to DevOps isn't always recognized. The 2014 DevOps Survey of Practice shows that one of the key predictors of DevOps success is putting all production environment artifacts into version control. In this eSeminar, Gene Kim will discuss these survey findings and will share woeful tales of artifact management gone wrong! Gene will also share examples of how …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds