maj030598
asked on
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?
I don't think it can be done with CList. Use list template class in STL instead. It has a member function sort.
ASKER
It always can be done!!!
This article was contributed by Douglas Peterson.
// SortableObList.h
////////////////////////// ////////// ////////// ////////// ////////// ///
class CSortableObList : public CObList
{
public:
CSortableObList(int nBlockSize = 10) : CObList(nBlockSize) { }
void Sort(int(*CompareFunc)(COb ject* 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::Ge tHead(); }
TYPE GetHead() const
{ return (TYPE)CSortableObList::Get Head(); }
TYPE& GetTail()
{ return (TYPE&)CSortableObList::Ge tTail(); }
TYPE GetTail() const
{ return (TYPE)CSortableObList::Get Tail(); }
// get head or tail (and remove it) - don't call on empty list!
TYPE RemoveHead()
{ return (TYPE)CSortableObList::Rem oveHead(); }
TYPE RemoveTail()
{ return (TYPE)CSortableObList::Rem oveTail(); }
// add before head or after tail
POSITION AddHead(TYPE newElement)
{ return CSortableObList::AddHead(n ewElement) ; }
POSITION AddTail(TYPE newElement)
{ return CSortableObList::AddTail(n ewElement) ; }
// add another list of elements before head or after tail
void AddHead(CTypedSortableObLi st< TYPE >* pNewList)
{ CSortableObList::AddHead(p NewList); }
void AddTail(CTypedSortableObLi st< TYPE >* pNewList)
{ CSortableObList::AddTail(p NewList); }
// iteration
TYPE& GetNext(POSITION& rPosition)
{ return (TYPE&)CSortableObList::Ge tNext(rPos ition); }
TYPE GetNext(POSITION& rPosition) const
{ return (TYPE)CSortableObList::Get Next(rPosi tion); }
TYPE& GetPrev(POSITION& rPosition)
{ return (TYPE&)CSortableObList::Ge tPrev(rPos ition); }
TYPE GetPrev(POSITION& rPosition) const
{ return (TYPE)CSortableObList::Get Prev(rPosi tion); }
// getting/modifying an element at a given position
TYPE& GetAt(POSITION position)
{ return (TYPE&)CSortableObList::Ge tAt(positi on); }
TYPE GetAt(POSITION position) const
{ return (TYPE)CSortableObList::Get At(positio n); }
void SetAt(POSITION pos, TYPE newElement)
{ CSortableObList::SetAt(pos , newElement); }
void Sort( int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )
{ CSortableObList::Sort((int (*)(CObjec t*,CObject *))Compare Func); }
void Sort( POSITION posStart, int iElements, int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )
{ CSortableObList::Sort(posS tart, iElements, (int(*)(CObject*,CObject*) )CompareFu nc); }
};
// 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->da ta,pOtemp) > 0; pNj = pNj->pPrev)
pNj->data = pNj->pPrev->data;
// Insert data pointer into it's proper position
pNj->data = pOtemp;
}
}
void CSortableObList::Sort(POSI TION 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*)p osStart, 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->da ta,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*)pFir stObj)->na me,((CMyOb ject*)pSec ondObj)->n ame);
}
};
// 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::CompB ackward);
// 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);
}
// SortableObList.h
//////////////////////////
class CSortableObList : public CObList
{
public:
CSortableObList(int nBlockSize = 10) : CObList(nBlockSize) { }
void Sort(int(*CompareFunc)(COb
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::Ge
TYPE GetHead() const
{ return (TYPE)CSortableObList::Get
TYPE& GetTail()
{ return (TYPE&)CSortableObList::Ge
TYPE GetTail() const
{ return (TYPE)CSortableObList::Get
// get head or tail (and remove it) - don't call on empty list!
TYPE RemoveHead()
{ return (TYPE)CSortableObList::Rem
TYPE RemoveTail()
{ return (TYPE)CSortableObList::Rem
// add before head or after tail
POSITION AddHead(TYPE newElement)
{ return CSortableObList::AddHead(n
POSITION AddTail(TYPE newElement)
{ return CSortableObList::AddTail(n
// add another list of elements before head or after tail
void AddHead(CTypedSortableObLi
{ CSortableObList::AddHead(p
void AddTail(CTypedSortableObLi
{ CSortableObList::AddTail(p
// iteration
TYPE& GetNext(POSITION& rPosition)
{ return (TYPE&)CSortableObList::Ge
TYPE GetNext(POSITION& rPosition) const
{ return (TYPE)CSortableObList::Get
TYPE& GetPrev(POSITION& rPosition)
{ return (TYPE&)CSortableObList::Ge
TYPE GetPrev(POSITION& rPosition) const
{ return (TYPE)CSortableObList::Get
// getting/modifying an element at a given position
TYPE& GetAt(POSITION position)
{ return (TYPE&)CSortableObList::Ge
TYPE GetAt(POSITION position) const
{ return (TYPE)CSortableObList::Get
void SetAt(POSITION pos, TYPE newElement)
{ CSortableObList::SetAt(pos
void Sort( int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )
{ CSortableObList::Sort((int
void Sort( POSITION posStart, int iElements, int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )
{ CSortableObList::Sort(posS
};
// 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->da
pNj->data = pNj->pPrev->data;
// Insert data pointer into it's proper position
pNj->data = pOtemp;
}
}
void CSortableObList::Sort(POSI
{
// 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
// 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;
{
// 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
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*)pFir
}
};
// 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::CompB
// 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);
}
ASKER
I am looking for quick sort, I have written bubble and insertion sort, I want to use quicksort for CList.
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?
ASKER
Thanx a lot, I have written a quick sort function CList.
Do you still need help, or did you mean to delete your question?
.B ekiM
.B ekiM
ASKER
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);//thes e two functions are
posj = m_Node.FindIndex(j);//cost ly 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(pos i);m_Node. GetPrev(po sj);
}//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
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);//thes
posj = m_Node.FindIndex(j);//cost
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_
i++;j--;m_Node.GetNext(pos
}//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
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
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
Quicksort has slow performance on a sequential-access structure like a linked list. Other algorithms like Insertion sort are perhaps much realistic.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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,pos r);
}
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(pos j));
}
// 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);
}
void qsort (CList <CRecord,CRecord&> &list)
{
// call helper to srto entire array
POSITION posl = list.GetHeadPosition();
POSITION posr = list.GetTailPosition();
qsort_helper(list,posl,pos
}
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
}
// 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);
}