Sortable CObArray class

.


// SortableObArray.h
/////////////////////////////////////////////////////////////////////

class CSortableObArray : public CObArray
{
public:
	void Sort(int(*CompareFunc)(CObject* pFirst, CObject* pSecond));
	void Sort(int iStartPos, int iElements, int(*CompareFunc)(CObject* pFirst, CObject* pSecond));
};


template< class TYPE >
class CTypedSortableObArray : public CSortableObArray
{
public:
	// Accessing elements
	TYPE GetAt(int nIndex) const
	{ return (TYPE)CSortableObArray::GetAt(nIndex); }
	TYPE& ElementAt(int nIndex)
	{ return (TYPE&)CSortableObArray::ElementAt(nIndex); }
	void SetAt(int nIndex, TYPE ptr)
	{ CSortableObArray::SetAt(nIndex, ptr); }
	
	// Potentially growing the array
	void SetAtGrow(int nIndex, TYPE newElement)
	{ CSortableObArray::SetAtGrow(nIndex, newElement); }
	int Add(TYPE newElement)
	{ return CSortableObArray::Add(newElement); }
	int Append(const CTypedPtrArray< CSortableObArray, TYPE >& src)
	{ return CSortableObArray::Append(src); }
	void Copy(const CTypedPtrArray< CSortableObArray, TYPE >& src)
	{ CSortableObArray::Copy(src); }
	
	// Operations that move elements around
	void InsertAt(int nIndex, TYPE newElement, int nCount = 1)
	{ CSortableObArray::InsertAt(nIndex, newElement, nCount); }
	void InsertAt(int nStartIndex, CTypedSortableObArray< TYPE >* pNewArray)
	{ CSortableObArray::InsertAt(nStartIndex, pNewArray); }
	
	// overloaded operator helpers
	TYPE operator[](int nIndex) const
	{ return (TYPE)CSortableObArray::operator[](nIndex); }
	TYPE& operator[](int nIndex)
	{ return (TYPE&)CSortableObArray::operator[](nIndex); }
	
	void Sort( int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )
	{ CSortableObArray::Sort((int(*)(CObject*,CObject*))CompareFunc); }
	void Sort( int iStartPos, int iElements, int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )
	{ CSortableObArray::Sort(iStartPos, iElements, (int(*)(CObject*,CObject*))CompareFunc); }
};



// SortableObArray.cpp
///////////////////////////////////////////////////////////////////

#define STRIDE_FACTOR 3

void CSortableObArray::Sort(int(*CompareFunc)(CObject* pFirst, CObject* pSecond))
{
	// CompareFunc is expected to return a positive integer if pFirstObj
	// should follow pSecondObj (is greater than)
	
	// Uses Shell Sort
	
	// Basically it does a bunch of smaller insertion sorts than insertion sorts the
	//  whole thing.  Insertion sorting is much faster on a list that is already
	//  mostly sorted.
	
	// ** NOTE:  Because GetSize() is called to retrieve the number of elements, you should
	//            call SetSize() with the number of valid elements.  An alternative is
	//            shown in the sort function below.
	
	ASSERT_VALID(this);
	
	BOOL bFound;
	int iElements = GetSize();
	int iInner,iOuter,iStride = 1;
	CObject *pTmp;
	
	while (iStride <= iElements)
		iStride = iStride * STRIDE_FACTOR + 1;
	
	while (iStride > (STRIDE_FACTOR - 1))
	{
		iStride = iStride / STRIDE_FACTOR;
		for (iOuter = iStride; iOuter < iElements; iOuter++)
		{
			bFound = 0;
			iInner = iOuter - iStride;
			while ((iInner >= 0) && !bFound)
			{
				if (CompareFunc(m_pData[iInner+iStride],m_pData[iInner]) < 0)
				{
					pTmp = m_pData[iInner+iStride];
					m_pData[iInner+iStride] = m_pData[iInner];
					m_pData[iInner] = pTmp;
					iInner -= iStride;
				}
				else
					bFound = 1;
			}
		}
	}
}

void CSortableObArray::Sort(int iStartPos, int iElements, int(*CompareFunc)(CObject* pFirst, CObject* pSecond))
{
	// This variation allows you to sort only a portion of the array
	
	ASSERT_VALID(this);
	ASSERT( iStartPos >= 0 && iStartPos <= GetUpperBound() );
	ASSERT( GetSize() - iStartPos >= iElements );
	
	BOOL bFound;
	int iInner,iOuter,iStride = 1;
	CObject *pTmp;
	CObject **pData = &m_pData[iStartPos];
	
	while (iStride <= iElements)
		iStride = iStride * STRIDE_FACTOR + 1;
	
	while (iStride > (STRIDE_FACTOR - 1))
	{
		iStride = iStride / STRIDE_FACTOR;
		for (iOuter = iStride; iOuter < iElements; iOuter++)
		{
			bFound = 0;
			iInner = iOuter - iStride;
			while ((iInner >= 0) && !bFound)
			{
				if (CompareFunc(pData[iInner+iStride],pData[iInner]) < 0)
				{
					pTmp = pData[iInner+iStride];
					pData[iInner+iStride] = pData[iInner];
					pData[iInner] = pTmp;
					iInner -= iStride;
				}
				else
					bFound = 1;
			}
		}
	}
}



// Usage
//////////////////////////////////////////////////////////

// Create a CObject based class
class CMyObject : public CObject
{
public:
    CString name;
    static int CompBackward(CMyObject* pFirstObj, CMyObject* pSecondObj)
    {
        return -lstrcmp((LPCTSTR)pFirstObj->name,(LPCTSTR)pSecondObj->name);
    }
};

// Create an array object
CTypedSortableObArray< CMyObject* > array;

array.SetSize(10);

// Fill the array with a bunch of objects
for (int i=0; i < 10; i++)
{
	CMyObject * pObj = new CMyObject;
	pObj->name.Format("Object #%d",i);
	array[i] = pObj;
}

// Sort the array
array.Sort(CMyObject::CompBackward);

// Display the contents of the now sorted array
for (int i=0; i < 10; i++)
{
	TRACE1("%s\n",array[i]->name);
}




Comments

  • Appreciations

    Posted by Legacy on 08/10/2000 12:00am

    Originally posted by: Christoph Platz

    Thank you very much for this! It works excellent.

    Reply
  • Excellent! A couple compile tips for potential users...

    Posted by Legacy on 04/18/2000 12:00am

    Originally posted by: David Emery

    Many thanks to Douglas Peterson for his contribution. I was in need of a class like this, but was too lazy to write it myself...

    In order to compile with VC5 SP3, I added to the following:

    to Stdafx.h:

    #include <afxtempl.h>

    to SortableObArray.h

    #if _MSC_VER >= 1000
    #pragma once
    #endif // _MSC_VER >= 1000

    Thanks Douglas!

    Reply
  • What is shell sort?

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

    Originally posted by: Arnt Witteveen

    What is shell sort? Is it a decent sorting algorith as far as speed goes? Is better/worse than quicksort?

    Reply
  • This class is great!!!

    Posted by Legacy on 07/27/1999 12:00am

    Originally posted by: Olafur Bergsson

    Just wanted to express my liking of this class ... works great for me.

    I use it to represent a list of mixed Dbrecord and fake text Items in a Virtual ListCtrl. Man it's fast :)

    Reply
  • There's a problem with the documentation of CompareFunc

    Posted by Legacy on 04/29/1999 12:00am

    Originally posted by: Paul Hanley

    In the class it says:

    // CompareFunc is expected to return a positive integer if pFirstObj
    // should follow pSecondObj (is greater than)

    In reality, it's expecting CompareFunc to return a negative integer if pFirstObj should go before pSecondObj (is less than).


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

Top White Papers and Webcasts

  • U.S. companies are desperately trying to recruit and hire skilled software engineers and developers, but there is simply not enough quality talent to go around. Tiempo Development is a nearshore software development company. Our headquarters are in AZ, but we are a pioneer and leader in outsourcing to Mexico, based on our three software development centers there. We have a proven process and we are experts at providing our customers with powerful solutions. We transform ideas into reality.

  • When individual departments procure cloud service for their own use, they usually don't consider the hazardous organization-wide implications. Read this paper to learn best practices for setting up an internal, IT-based cloud brokerage function that service the entire organization. Find out how this approach enables you to retain top-down visibility and control of network security and manage the impact of cloud traffic on your WAN.

Most Popular Programming Stories

More for Developers

RSS Feeds

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