Aleksey.M
BAN USERYep, the mentioned algo is not absolutely correct.
E.g. it shouldn't do pop(top) - push(current) in case of (there are more than one element in the stack and current.data > top.data). Otherwise the stack won't contain swapped elements at the end of the BST traversal procedure.
There is one importnant from my perspective thing (which I was not familar with previously): if the algo uses n additional bits it is considered to use O(1) additional space anyway. (Since a representation of at least number 'n' requires log(n) bits.)
So we could just mark already swapped numbers in the array doing cycles and do not start the cycle for those numbers which are already marked. Result: O(n) times (for n-2 swaps) and O(1) space (for n bits).
template <class T>
void SLList<T>::JoinSimilar()
{
LLNode<int> *pCur = pHead;
if(!pCur || !pCur->pNext) return;
const int TABLE_SIZE = 10;
SLList<SLList<int>*> **AggList = new SLList<SLList<int>*>*[TABLE_SIZE]; // hash-table
for(int ind_table = 0; ind_table < TABLE_SIZE; ind_table++)
{
AggList[ind_table] = new SLList<SLList<int>*>; // each element of the table is
} // a pointer to the list of lists
LLNode<int> *pCurTblListNode = NULL, *pTmp = NULL;
LLNode<SLList<int>*> *pCurTblList = NULL, *pNewTblList = NULL;
while(pCur)
{
pCurTblList = AggList[pCur->iData%10]->pHead; // fill the table element
while(pCurTblList)
{
pCurTblListNode = (pCurTblList->iData)->pHead; // each element is the list of the lists of numbers,
if(pCurTblListNode->iData == pCur->iData) // which end with the same digit, e.g.
{ // 5->5->5->NULL
pTmp = pCur->pNext; // 35->35->NULL
pCur->pNext = pCurTblListNode; // 275->NULL
(pCurTblList->iData)->pHead = pCur; // NULL
pCur = pTmp;
break;
}
pCurTblList = pCurTblList->pNext;
}
if(!pCurTblList)
{
pNewTblList = new LLNode<SLList<int>*>;
pNewTblList->iData = new SLList<int>;
pNewTblList->pNext = AggList[pCur->iData%10]->pHead;
AggList[pCur->iData%10]->pHead = pNewTblList;
(pNewTblList->iData)->pHead = pCur;
pTmp = pCur->pNext;
pCur->pNext = NULL;
pCur = pTmp;
}
};
LLNode<int> *pFisrt = NULL, *pLast = NULL, *pLastTblList = NULL;
for(int ind_table = 0; ind_table < TABLE_SIZE; ind_table++) // join all the lists into one single list
{ // and then set the head of the base list to the
pCurTblList = AggList[ind_table]->pHead; // new joint list
while(pCurTblList)
{
if(!pFisrt)
{
pFisrt = (pCurTblList->iData)->pHead;
}
pLast = (pCurTblList->iData)->pHead;
if(pLastTblList)
{
pLastTblList->pNext = pLast;
}
while(pLast->pNext)
{
pLast = pLast->pNext;
};
if(pCurTblList->pNext)
{
pLast->pNext = ((pCurTblList->pNext)->iData)->pHead;
pLastTblList = NULL;
}
else
{
pLastTblList = pLast;
}
pCurTblList = pCurTblList->pNext;
}
}
pHead = pFisrt;
for(int ind_table = 0; ind_table < TABLE_SIZE; ind_table++)
{
delete AggList[ind_table];
}
void MergeSort(Node **before, Node **start, Node **end)
{
if(!*start || !*end) return; // in case of NULL
if(*start == *end) return; // there is only one element in the list
if((*start)->pNext == *end) // there are two elements in the list
{
Node *tmp = NULL;
if((*start)->iData > (*end)->iData) // exchange them if needed
{
tmp = *start; // it's important to change data by the given addresses
(*before)->pNext = (*end);
*start = *end;
*end = tmp;
(*end)->pNext = (*start)->pNext;
(*start)->pNext = *end;
}
return;
}
Node *pFast = *start, *middle = *start;
if(!*start || !(*start)->pNext || !(*start)->pNext->pNext)
{
middle = *start;
}
else
{
while(pFast && pFast != (*end)) // finding the middle
{
pFast = pFast->pNext;
if(pFast)
{
pFast = pFast->pNext;
if(pFast)
{
middle = middle->pNext;
}
}
}
}
MergeSort(before, start, &middle); // recursive call for the first part of the list
MergeSort(&middle, &(middle->pNext), end); // recursive call for the last part of the list
Node *pNewLast = NULL, *pLefLast = *start, *pRightLast = middle->pNext;
if(pLefLast->iData <= pRightLast->iData) // set the last elemnt for the new merged list
{ // At the moment it is the fisrt elemnt for the
pNewLast = pLefLast; // new merged list
pLefLast = pLefLast->pNext;
}
else
{
middle->pNext = pRightLast->pNext;
pNewLast = pRightLast;
(*before)->pNext = pRightLast;
pRightLast = pRightLast->pNext;
}
(*start) = (*before)->pNext; // it's important to set new data by the adress of the 'start' element
while(pLefLast != middle->pNext && pRightLast != NULL && pRightLast != (*end)->pNext)
{ // cycle to merge two sorted lists
if(pLefLast->iData <= pRightLast->iData)
{
pNewLast->pNext = pLefLast;
pNewLast = pNewLast->pNext;
pLefLast = pLefLast->pNext;
}
else
{
middle->pNext = pRightLast->pNext;
pNewLast->pNext = pRightLast;
pNewLast = pNewLast->pNext;
pRightLast = pRightLast->pNext;
}
}
if(pLefLast == middle->pNext) // merging the remainders if needed
{
pNewLast->pNext = pRightLast;
}
else if((pRightLast == (*end)->pNext)||(pRightLast == NULL))
{ // merging the remainders if needed
pNewLast->pNext = pLefLast;
(*end) = middle; //it's important to set new data by the adress of the 'end' element
}
}
void sort(){
Node *pEnd = NULL, *pAxPtr = new Node;
pEnd = LList->pHead;
while(pEnd->pNext)pEnd = pEnd->pNext;
pAxPtr->pNext = LList->pHead;
LList->MergeSort(&pAxPtr, &(LList->pHead), &pEnd);
LList->pHead = pAxPtr->pNext;
delete pAxPtr;
}
200-elements array can be kept in L1 cache (which is effectively the fastest computer memory) entirely, while 200-elements tree with high probability can not be kept there (a tree is fragmented beacuse of memory block for each node is usually allocated separetely from the heap).
- Aleksey.M November 28, 2012