Click here to Skip to main content
11,703,617 members (71,327 online)
Click here to Skip to main content

Tagged as

QuickSort enabled CArray template class

, 16 Mar 2000 138K 3K 30
Rate this:
Please Sign up or sign in to vote.
A CArray derived class that provides quick and convenient sorting
  • Download demo project - 15 Kb
  • Download source files - 2 Kb
  • 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 isqsort() 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.

    License

    This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

    A list of licenses authors might use can be found here

    Share

    About the Author

    Martin Ziacek
    Software Developer (Senior)
    United Kingdom United Kingdom
    No Biography provided

    You may also be interested in...

    Comments and Discussions

     
    GeneralLicense Pin
    Member 138541815-Sep-10 21:31
    memberMember 138541815-Sep-10 21:31 
    QuestionTerm of use for Qarray.h Pin
    ofe26-Aug-09 4:30
    memberofe26-Aug-09 4:30 
    GeneralPointers Pin
    Dean Wyant5-Dec-08 9:03
    memberDean Wyant5-Dec-08 9:03 
    QuestionDoes not sort records? Pin
    al25004-Jul-07 8:34
    memberal25004-Jul-07 8:34 
    AnswerRe: Does not sort records? Pin
    Dean Wyant5-Dec-08 10:55
    memberDean Wyant5-Dec-08 10:55 
    Questionvisual studio 2005 Pin
    alexch00729-May-07 1:31
    memberalexch00729-May-07 1:31 
    Generalqsort+bsearch Pin
    itkid20-Apr-05 20:40
    memberitkid20-Apr-05 20:40 
    Generalnice one thanks Pin
    Hirosh28-Feb-03 2:10
    memberHirosh28-Feb-03 2:10 
    GeneralCArray use Pin
    Manal E. Helal3-Oct-00 1:49
    sussManal E. Helal3-Oct-00 1:49 
    GeneralHelp Pin
    Peter Wong23-Aug-00 23:51
    sussPeter Wong23-Aug-00 23:51 
    GeneralRe: Help Pin
    Martin Ziacek24-Aug-00 1:46
    sussMartin Ziacek24-Aug-00 1:46 
    Generalno header file!! Pin
    Vivek3-Aug-00 10:35
    sussVivek3-Aug-00 10:35 
    GeneralRe: no header file!! Pin
    Martin Ziacek3-Aug-00 19:51
    sussMartin Ziacek3-Aug-00 19:51 
    GeneralIssues with this article Pin
    Ken Nicolson5-Apr-00 20:14
    sussKen Nicolson5-Apr-00 20:14 
    GeneralRe: Issues with this article Pin
    Martin Ziacek6-Apr-00 21:55
    sussMartin Ziacek6-Apr-00 21:55 
    GeneralRe: Issues with this article Pin
    Ken Nicolson6-Apr-00 22:59
    sussKen Nicolson6-Apr-00 22:59 
    GeneralRe: Issues with this article Pin
    Kevin McFarlane8-Oct-04 11:07
    memberKevin McFarlane8-Oct-04 11:07 

    General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

    Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

    | Advertise | Privacy | Terms of Use | Mobile
    Web01 | 2.8.150819.1 | Last Updated 17 Mar 2000
    Article Copyright 2000 by Martin Ziacek
    Everything else Copyright © CodeProject, 1999-2015
    Layout: fixed | fluid