Click here to Skip to main content
Click here to Skip to main content

Tagged as

Using qsort on arrays of sequential data

, , 26 Jan 2000 CPOL
Rate this:
Please Sign up or sign in to vote.
An introduction to a useful function
  • Download demo project - 14 Kb
  • <!-- Article Starts -->

    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 Value Description
    < 0 elem1 less than elem2
    0 elem1 equivalent to elem2
    > 0 elem1 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)

    Share

    About the Authors

    Chris Maunder
    Founder CodeProject
    Canada Canada
    Chris is the Co-founder, Administrator, Architect, Chief Editor and Shameless Hack who wrote and runs The Code Project. He's been programming since 1988 while pretending to be, in various guises, an astrophysicist, mathematician, physicist, hydrologist, geomorphologist, defence intelligence researcher and then, when all that got a bit rough on the nerves, a web developer. He is a Microsoft Visual C++ MVP both globally and for Canada locally.
     
    His programming experience includes C/C++, C#, SQL, MFC, ASP, ASP.NET, and far, far too much FORTRAN. He has worked on PocketPCs, AIX mainframes, Sun workstations, and a CRAY YMP C90 behemoth but finds notebooks take up less desk space.
     
    He dodges, he weaves, and he never gets enough sleep. He is kind to small animals.
     
    Chris was born and bred in Australia but splits his time between Toronto and Melbourne, depending on the weather. For relaxation he is into road cycling, snowboarding, rock climbing, and storm chasing.
    Follow on   Twitter   Google+   LinkedIn

    Phil McGahan

    United States United States
    No Biography provided

    Comments and Discussions

     
    GeneralPointer on CPtrArray Pinmemberrepsac25-Aug-04 20:09 
    Nice article about the qsort which works great. I had some trouble sorting a CPtrArray - hence this post. Add the cast to a pointer-to-pointer as shown below:
    // file is the class/struct/whatever
    // contained in the CPtrArray
    file** ppFileTmp1 = (file**)p1;
    file** ppFileTmp2 = (file**)p2;

    file* q1 = *ppFileTmp1;
    file* q2 = *ppFileTmp2;
    GeneralRe: Pointer on CPtrArray PinsussBorislav Sabev17-Jan-05 2:49 
    GeneralRe: Pointer on CPtrArray PinmemberFlaviu218-Mar-12 9:02 
    GeneralI like this code... PinmemberJonathan Craig7-Mar-02 4:25 
    GeneralProblem with similar code when sorting CStringArray Pinsusschris27-Jun-00 11:45 
    GeneralRe: Problem with similar code when sorting CStringArray PinmemberMcGahanFL18-May-03 7:25 
    Generalqsort is not a good choice in C++ PinsussWilliam Kempf28-Jan-00 4:05 
    GeneralRe: qsort is not a good choice in C++ PinmemberMichael Cowperthwaite5-Jul-01 10:32 
    GeneralRe: qsort is not a good choice in C++ PinmemberJean-Marc16-Jan-02 23:33 

    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
    Web03 | 2.8.141030.1 | Last Updated 27 Jan 2000
    Article Copyright 2000 by Chris Maunder, Phil McGahan
    Everything else Copyright © CodeProject, 1999-2014
    Layout: fixed | fluid