Solved

Quick Sort and CList

Posted on 1998-04-01
12
1,865 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
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
Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

 

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 50 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

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Complete beginner needs help making a cron job 9 125
iSeries DB2 Query 2 97
maxBlock challenge 30 142
Updating statistics with error notification email in SQL server 4 109
Introduction: Load and Save to file, Document-View interaction inside the SDI. Continuing from the second article about sudoku.   Open the project in visual studio. From the class view select CSudokuDoc and double click to open the header …
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.

860 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