Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Quick Sort and CList

Posted on 1998-04-01
12
Medium Priority
?
1,981 Views
Last Modified: 2013-11-20
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?
0
Comment
Question by:maj030598
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 2
  • 2
  • +3
12 Comments
 
LVL 23

Expert Comment

by:chensu
ID: 1317382
I don't think it can be done with CList. Use list template class in STL instead. It has a member function sort.
0
 

Author Comment

by:maj030598
ID: 1317383
It always can be done!!!
0
 

Expert Comment

by:scroll0
ID: 1317384
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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

Author Comment

by:maj030598
ID: 1317385
I am looking for quick sort, I have written bubble and insertion sort, I want to use quicksort for CList.
0
 
LVL 23

Expert Comment

by:chensu
ID: 1317386
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
 

Author Comment

by:maj030598
ID: 1317387
Thanx a lot, I have written a quick sort function CList.

0
 
LVL 11

Expert Comment

by:mikeblas
ID: 1317388
Do you still need help, or did you mean to delete your question?

.B ekiM
0
 

Author Comment

by:maj030598
ID: 1317389
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
 
LVL 11

Expert Comment

by:mikeblas
ID: 1317390
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
 

Expert Comment

by:directG
ID: 1317391
Quicksort has slow performance on a sequential-access structure like a linked list. Other algorithms like Insertion sort are perhaps much realistic.
0
 
LVL 10

Accepted Solution

by:
RONSLOW earned 200 total points
ID: 1317392
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
 
LVL 10

Expert Comment

by:RONSLOW
ID: 1317393
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

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This is to be the first in a series of articles demonstrating the development of a complete windows based application using the MFC classes.  I’ll try to keep each article focused on one (or a couple) of the tasks that one may meet.   Introductio…
Introduction: Database storage, where is the exe actually on the disc? Playing a game selected randomly (how to generate random numbers).  Error trapping with try..catch to help the code run even if something goes wrong. Continuing from the seve…
This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.
Is your data getting by on basic protection measures? In today’s climate of debilitating malware and ransomware—like WannaCry—that may not be enough. You need to establish more than basics, like a recovery plan that protects both data and endpoints.…
Suggested Courses

636 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question