Solved

# Quick Sort and CList

Posted on 1998-04-01
1,810 Views
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
Question by:maj030598
• 4
• 2
• 2
• +3

LVL 23

Expert Comment

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

It always can be done!!!
0

Expert Comment

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
{ return (TYPE&)CSortableObList::GetHead(); }
{ 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!
{ return (TYPE)CSortableObList::RemoveHead(); }
TYPE RemoveTail()
{ return (TYPE)CSortableObList::RemoveTail(); }

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

// add another list of elements before head or after tail
void AddTail(CTypedSortableObList< TYPE >* 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);
}

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

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

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

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

0

LVL 11

Expert Comment

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

.B ekiM
0

Author Comment

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

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

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

RONSLOW earned 50 total points
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

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

## Join & Write a Comment Already a member? Login.

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.

#### Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!