Solved

Quick Sort and CList

Posted on 1998-04-01
12
1,810 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
  • 4
  • 2
  • 2
  • +3
12 Comments
 
LVL 23

Expert Comment

by:chensu
Comment Utility
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
Comment Utility
It always can be done!!!
0
 

Expert Comment

by:scroll0
Comment Utility
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
 

Author Comment

by:maj030598
Comment Utility
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
Comment Utility
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
Comment Utility
Thanx a lot, I have written a quick sort function CList.

0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 11

Expert Comment

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

.B ekiM
0
 

Author Comment

by:maj030598
Comment Utility
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
Comment Utility
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
Comment Utility
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 50 total points
Comment Utility
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
Comment Utility
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Here is how to use MFC's automatic Radio Button handling in your dialog boxes and forms.  Beginner programmers usually start with a OnClick handler for each radio button and that's just not the right way to go.  MFC has a very cool system for handli…
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…
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.
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…

743 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now