Click here to Skip to main content
15,867,568 members
Articles / Desktop Programming / MFC
Article

Using qsort on arrays of sequential data

,
Rate me:
Please Sign up or sign in to vote.
3.58/5 (6 votes)
26 Jan 2000CPOL 108K   782   33   9
An introduction to a useful function
  • Download demo project - 14 Kb
  • Introduction

    qsort is part of the C and C++ language. It is a quick sort algorithm that is both fast and easy to implement. It is a recursive algorithm, but it is surprising fast. (30,000 items in about a fourth of a second on a PII-333 machine.)

    This 'How To' demonstrates the use of qsort on a CArray. However, it would work just as well on any other sequential data structure. Static arrays, CStringArray, CPtrArray or something of your own creation.

    The demo project is written in VC 5.0. It has not been plagiarized from any other source. There are no restrictions on the source.

    Sorting

    Suppose you wanted to store and sort number of items of type CArrayClass, defined as follows:
    class CArrayClass  
    {
    public:
    	CArrayClass();
    	virtual ~CArrayClass();
    	
    	WORD    m_wMsgId;
    	CString m_strMsgType;
    };

    Using the CArray template class we can store the CArrayClass objects using the following array declaration

    typedef CArray<CArrayClass, CArrayClass&> Type_aCArrayClass;
    Type_aCArrayClass m_aCArrayClass;

    To use qsort you need to declare a callback function whose address is known at compile time - meaning it must either be a global or static function. The qsort callback function must be defined as:

    int (__cdecl *compare )(const void *elem1, const void *elem2 )

    Items elem1 and elem2 are pointers to two items in the array, and must be cast to the appropriate type and compared. The return value of the function is as follows:

    Return ValueDescription
    < 0elem1 less than elem2
    0elem1 equivalent to elem2
    > 0elem1 greater than elem2

    In our case the callback function would look like the following:

    //This function can be global or it can be a static member of your class,
    //but it's address must be know at compile time.
    int CCArrayExampleDlg::SortTheArray(void* p1,void* p2)
    {
    	short n=0;
    	CArrayClass* a1 = (CArrayClass*)p1;
    	CArrayClass* a2 =  (CArrayClass*)p2; // If we were sorting a CPtrArray then we 
    	                                     // would have to do a second level 
    	                                     // of casting to get to the data keys that we 
    	                                     // would be sorting.
    
    	if (a1->m_strMsgType  <a2->m_strMsgType)	//Ascending
    		n = -1; 
    	elseif (a1->m_strMsgType  >a2->m_strMsgType)
    		n = 1; 
    	elseif(a1->m_wMsgId  <a2->m_wMsgId)	//Ascending
    		n = -1; 
    	elseif(a1->m_wMsgId  >a2->m_wMsgId)
    		n = 1;
    
    	return n;
    }

    To use this sort callback we need to fill the array, call qsort and then display the results.

    void CCArrayExampleDlg::OnSort() 
    { 
    	// Fill the array m_aCArrayClass with items of type CArrayClass 
    	...
    
    	// Sort the array 
    	if(m_aCArrayClass.GetSize() >  0) 
    	{
    		qsort((void*)&m_aCArrayClass[0],
    		      (size_t)m_aCArrayClass.GetSize(), 
    		      sizeof(CArrayClass),
    		      (int(*)(const void*, const void*))CCArrayExampleDlg::SortTheArray);
    	}
    	
    	// Display the newly sorted array
    	...
    }

    License

    This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


    Written By
    Founder CodeProject
    Canada Canada
    Chris Maunder is the co-founder of CodeProject and ContentLab.com, and has been a prominent figure in the software development community for nearly 30 years. Hailing from Australia, Chris has a background in Mathematics, Astrophysics, Environmental Engineering and Defence Research. His programming endeavours span everything from FORTRAN on Super Computers, C++/MFC on Windows, through to to high-load .NET web applications and Python AI applications on everything from macOS to a Raspberry Pi. Chris is a full-stack developer who is as comfortable with SQL as he is with CSS.

    In the late 1990s, he and his business partner David Cunningham recognized the need for a platform that would facilitate knowledge-sharing among developers, leading to the establishment of CodeProject.com in 1999. Chris's expertise in programming and his passion for fostering a collaborative environment have played a pivotal role in the success of CodeProject.com. Over the years, the website has grown into a vibrant community where programmers worldwide can connect, exchange ideas, and find solutions to coding challenges. Chris is a prolific contributor to the developer community through his articles and tutorials, and his latest passion project, CodeProject.AI.

    In addition to his work with CodeProject.com, Chris co-founded ContentLab and DeveloperMedia, two projects focussed on helping companies make their Software Projects a success. Chris's roles included Product Development, Content Creation, Client Satisfaction and Systems Automation.

    Written By
    United States United States
    This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

    Comments and Discussions

     
    GeneralPointer on CPtrArray Pin
    repsac25-Aug-04 20:09
    repsac25-Aug-04 20:09 
    GeneralRe: Pointer on CPtrArray Pin
    Borislav Sabev17-Jan-05 2:49
    sussBorislav Sabev17-Jan-05 2:49 
    GeneralRe: Pointer on CPtrArray Pin
    _Flaviu18-Mar-12 9:02
    _Flaviu18-Mar-12 9:02 
    GeneralI like this code... Pin
    Jonathan Craig7-Mar-02 4:25
    Jonathan Craig7-Mar-02 4:25 
    GeneralProblem with similar code when sorting CStringArray Pin
    Member 91427-Jun-00 11:45
    Member 91427-Jun-00 11:45 
    GeneralRe: Problem with similar code when sorting CStringArray Pin
    mcgahanfl18-May-03 7:25
    mcgahanfl18-May-03 7:25 
    Generalqsort is not a good choice in C++ Pin
    William Kempf28-Jan-00 4:05
    sussWilliam Kempf28-Jan-00 4:05 
    The qsort function is C based, and so isn't typesafe. The C++ algorithm std::sort will usually outperform qsort and is typesafe, not to mention much easier to use
    GeneralRe: qsort is not a good choice in C++ Pin
    5-Jul-01 10:32
    suss5-Jul-01 10:32 
    GeneralRe: qsort is not a good choice in C++ Pin
    16-Jan-02 23:33
    suss16-Jan-02 23:33 

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

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