Quick Sort and CList

It always can be done!!!

This article was contributed by Douglas Peterson.



// SortableObList.h
/////////////////////////////////////////////////////////////////////

class CSortableObList : public CObList
{
public:
      CSortableObList(int nBlockSize = 10) : CObList(nBlockSize) { }

      void Sort(int(*CompareFunc)(CObject* pFirstObj, CObject*pSecondObj));
      void Sort(POSITION posStart, int iElements, int (*CompareFunc)(CObject* pFirstObj, CObject* pSecondObj));
};


template< class TYPE >
class CTypedSortableObList : public CSortableObList
{
public:
// Construction
      CTypedSortableObList(int nBlockSize = 10) : CSortableObList(nBlockSize) { }

      // peek at head or tail
      TYPE& GetHead()
            { return (TYPE&)CSortableObList::GetHead(); }
      TYPE GetHead() const
            { return (TYPE)CSortableObList::GetHead(); }
      TYPE& GetTail()
            { return (TYPE&)CSortableObList::GetTail(); }
      TYPE GetTail() const
            { return (TYPE)CSortableObList::GetTail(); }

      // get head or tail (and remove it) - don't call on empty list!
      TYPE RemoveHead()
            { return (TYPE)CSortableObList::RemoveHead(); }
      TYPE RemoveTail()
            { return (TYPE)CSortableObList::RemoveTail(); }

      // add before head or after tail
      POSITION AddHead(TYPE newElement)
            { return CSortableObList::AddHead(newElement); }
      POSITION AddTail(TYPE newElement)
            { return CSortableObList::AddTail(newElement); }

      // add another list of elements before head or after tail
      void AddHead(CTypedSortableObList< TYPE >* pNewList)
            { CSortableObList::AddHead(pNewList); }
      void AddTail(CTypedSortableObList< TYPE >* pNewList)
            { CSortableObList::AddTail(pNewList); }

      // iteration
      TYPE& GetNext(POSITION& rPosition)
            { return (TYPE&)CSortableObList::GetNext(rPosition); }
      TYPE GetNext(POSITION& rPosition) const
            { return (TYPE)CSortableObList::GetNext(rPosition); }
      TYPE& GetPrev(POSITION& rPosition)
            { return (TYPE&)CSortableObList::GetPrev(rPosition); }
      TYPE GetPrev(POSITION& rPosition) const
            { return (TYPE)CSortableObList::GetPrev(rPosition); }

      // getting/modifying an element at a given position
      TYPE& GetAt(POSITION position)
            { return (TYPE&)CSortableObList::GetAt(position); }
      TYPE GetAt(POSITION position) const
            { return (TYPE)CSortableObList::GetAt(position); }
      void SetAt(POSITION pos, TYPE newElement)
            { CSortableObList::SetAt(pos, newElement); }

      void Sort( int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )
            { CSortableObList::Sort((int(*)(CObject*,CObject*))CompareFunc); }
      void Sort( POSITION posStart, int iElements, int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )
            { CSortableObList::Sort(posStart, iElements, (int(*)(CObject*,CObject*))CompareFunc); }
};


// SortableObList.cpp
///////////////////////////////////////////////////////////////////

void CSortableObList::Sort(int (*CompareFunc)(CObject* pFirstObj, CObject* pSecondObj))
{
      // CompareFunc is expected to return a positive integer if pFirstObj
      // should follow pSecondObj (is greater than)

      // Uses Insertion Sort

      // The Shell Sort is much faster than a straight insertion sort, however, it cannot
      //  be performed on a linked list (it COULD, but the resulting code would probably be
      //  much slower as a Shell Sort jumps all around the reletive positions of elements).

      // An Insertion Sort works by evaluating an item, if that item should
      // precede the item in front of it, than it shifts all the items that
      // should follow that item up one place until it finds the correct position
      // for the item, whereby it then 'inserts' that item.

      ASSERT_VALID(this);

      // If the list contains no items, the HEAD position will be NULL
      if (m_pNodeHead == NULL)
            return;

      CObject *pOtemp;
      CObList::CNode *pNi,*pNj;

      // Walk the list
      for (pNi = m_pNodeHead->pNext; pNi != NULL; pNi = pNi->pNext)
      {
            // Save data pointer
            pOtemp = pNi->data;

            // Walk the list backwards from pNi to the beginning of the list or until
            // the CompareFunc() determines that this item is in it's correct position
            // shifting all items upwards as it goes
            for (pNj = pNi; pNj->pPrev != NULL && CompareFunc(pNj->pPrev->data,pOtemp) > 0; pNj = pNj->pPrev)
                  pNj->data = pNj->pPrev->data;

            // Insert data pointer into it's proper position
            pNj->data = pOtemp;
      }

}

void CSortableObList::Sort(POSITION posStart, int iElements, int (*CompareFunc)(CObject* pFirstObj, CObject* pSecondObj))
{
      // This variation allows you to sort only a portion of the list

      // iElements can be larger than the number of remaining elements without harm
      // iElements can be -1 which will always sort to the end of the list

      ASSERT_VALID(this);
      ASSERT( AfxIsValidAddress((CObList::CNode*)posStart, sizeof(CObList::CNode)) );

      // Make certain posStart is a position value obtained by a GetHeadPosition or Find member function call
      //  as there is no way to test whether or not posStart is a valid CNode pointer from this list.
      // Ok, there is one way, we could walk the entire list and verify that posStart is in the chain, but even
      //  for debug builds that's a bit much.

      // If the list contains no items, the HEAD position will be NULL
      if (m_pNodeHead == NULL)
            return;

      CObject *pOtemp;
      CObList::CNode *pNi,*pNj;

      // Walk the list
      for (pNi = (CObList::CNode*)posStart; pNi != NULL && iElements != 0; pNi = pNi->pNext, iElements--)
      {
            // Save data pointer
            pOtemp = pNi->data;

            // Walk the list backwards from pNi to the beginning of the sort or until
            // the CompareFunc() determines that this item is in it's correct position
            // shifting all items upwards as it goes
            for (pNj = pNi; pNj->pPrev != NULL && pNj->pPrev != ((CObList::CNode*)posStart)->pPrev && CompareFunc(pNj->pPrev->data,pOtemp) > 0; pNj = pNj->pPrev)
                  pNj->data = pNj->pPrev->data;

            // Insert data pointer into it's proper position
            pNj->data = pOtemp;
      }

}



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

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

// Create a list object
CTypedSortableObList< CMyObject* > list;

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

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

// Display the contents of the now sorted list
for (POSITION pos = list.GetHeadPosition(); pos != NULL; )
{
     CMyObject* pObj = list.GetNext(pos);
     TRACE1("%s\n",pObj->name);
}

I am looking for quick sort, I have written bubble and insertion sort, I want to use quicksort for CList.

Yes, it always can be done. I meant that it could not be done directly. Why don't you use STL's list since it is already there?

Thanx a lot, I have written a quick sort function CList.

Do you still need help, or did you mean to delete your question?

.B ekiM

I think I still need help, Here is my code:
void qsort (CList <CRecord,CRecord&> &m_Node,long l,long r)
{
      long i,j,x;
      POSITION posi,posj;
      i=l;
      j=r;
      posi = m_Node.FindIndex(i);//these two functions are
      posj = m_Node.FindIndex(j);//costly anyway to optimize
      x = m_Node.GetAt(posi).x;
      do
      {
            while (m_Node.GetAt(posi).x < x) {m_Node.GetNext(posi);i++;}
            while (x < m_Node.GetAt(posj).x) {m_Node.GetPrev(posj);j--;}
            if (i<=j)
            {
                  swap(m_Node.GetAt(posi),m_Node.GetAt(posj));
                  i++;j--;m_Node.GetNext(posi);m_Node.GetPrev(posj);
            }//if
      }while ((i<j));
      if (l<j) qsort(m_Node,l,j);
      if (i<r) qsort(m_Node,i,r);

}
anyway to optimize the FindIndex functions

As you've noticed, finding an indexed element of a linked list is very expensive; it's an O(n) operation, unless you've indexed the list. But then you're just deferring the cost--you have to spend time on the indexing.

The short answer is that, to optimize your code, you shouldn't use a linked list--use an array, instead.  If you must use a linked list, you should use a sorting algorithm that's more friendly for lists.

.B ekiM

Quicksort has slow performance on a sequential-access structure like a linked list. Other algorithms like Insertion sort are perhaps much realistic.