Quick Sort and CList

How can I use quick sort with CList? I could not figure out how to use qsort with CList. Please can somebody point me to an algorithm?
maj030598Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

chensuCommented:
I don't think it can be done with CList. Use list template class in STL instead. It has a member function sort.
0
maj030598Author Commented:
It always can be done!!!
0
scroll0Commented:
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);
}


0
Get expert help—faster!

Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

maj030598Author Commented:
I am looking for quick sort, I have written bubble and insertion sort, I want to use quicksort for CList.
0
chensuCommented:
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?
0
maj030598Author Commented:
Thanx a lot, I have written a quick sort function CList.

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

.B ekiM
0
maj030598Author Commented:
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
0
mikeblasCommented:
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

0
directGCommented:
Quicksort has slow performance on a sequential-access structure like a linked list. Other algorithms like Insertion sort are perhaps much realistic.
0
RONSLOWCommented:
If you must use a list, it is probably best to sort the list as it is created.  As you insert each item, traverse the list to see where it belongs and add it at the corresponding place.

As for your quicksort, you shouldn't work with subscripts when working with lists, only work with POSITION pointers.  Start off with pointers to head and tail of the list.  Move the pointers in as per quicksort doing the exchange.  Then call recursively.

0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
RONSLOWCommented:
Perhaps this might work better...

void qsort (CList <CRecord,CRecord&> &list)
{
  // call helper to srto entire array
  POSITION posl = list.GetHeadPosition();
  POSITION posr = list.GetTailPosition();
  qsort_helper(list,posl,posr);
}
void qsort_helper (CList <CRecord,CRecord&> &list,POSITION posl,POSITION posr)
{
  // start from ends
  POSITION posi=posl,posj=posr;
  // compute partition value to be average of ends
  long xi = list.GetAt(posi).x;
  long xj = list.GetAt(posj).x;
  long x = (xi+xj)/2;
  // loop
  for (;;) {
    // move lower partition right
    while (posi != posj && list.GetAt(posi).x <= x) {
      list.GetNext(posi);
    }
    // move upper partition left
    while (posj != posi && x <= list.GetAt(posj).x) {
      list.GetPrev(posj);
    }
    // if we meet in the middle, stop
    if (posi == posj) break;
    // swap the wrongly positioned items
    swap(list.GetAt(posi),list.GetAt(posj));
  }
  // move out a bit
  while (posi != posl && x <= list.GetAt(posi).x) {
    list.GetPrev(posi);
  }
  while (posj != posr && list.GetAt(posj).x <= x) {
    list.GetNext(posj);
  }
  // recursively call helper to sort sublists
  if (posl != posj) qsort_helper (list,posl,posj);
  if (posi != posr) qsort_helper (list,posi,posr);
}

0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
System Programming

From novice to tech pro — start learning today.