Сортировка односвязного списка

[btf]

У меня есть класс списка:

Код: Выделить всё

struct node
{
int value;
node *next;
};

class cList
{
public:
 cList();
 ~cList();

 void Add(int value);
 void Delete();
 void DeleteAll();
 void Print();
 int GetCount() const;

private:
 node *Head;
 node *Tail;

 int itsCount;
};

cList::cList()
{
Head=Tail=NULL;
itsCount=0;
}

cList::~cList()
{
DeleteAll();
}

void cList::Add(int value)
{
node *temp=new node;

temp->value=value;
temp->next=NULL;
if(Head!=NULL)
 {
 Tail->next=temp;
 Tail=temp;
 }
else
 {
 Head=Tail=temp;
 }
itsCount++;
}

void cList: :D elete()
{
if(itsCount>0)
 {
 node *temp=Head;

 Head=Head->next;

 delete temp;

 itsCount--;
 }
else
 {
 cout<<"!!!ERROR: The list is empty. Nothing to delete!\n";
 }
}

void cList: :D eleteAll()
{
if(itsCount>0)
 {
 while(Head!=NULL)
 Delete();
 }
else
 {
 cout<<"!!!ERROR: The list is empty. Nothing to delete!\n";
 }
}

void cList::Print()
{
if(itsCount>0)
 {
 node *temp=Head;

 while(temp!=NULL)
  {
  cout<<temp->value<<" ";
  temp=temp->next;
  }

 cout<<"\n\n";
 }
else
 {
 cout<<"The list is empty\n";
 }
}

int cList::GetCount() const
{
return itsCount;
}

Надо добавить сюда метод сортировки списка, основанный на перестановке 2ух соседних элементов местами. Причем перестановка должна быть реализована методом обмена адресами.
Кому не турдно, напишите как это сделать, и если можно с комментариями.

[Albor]

что-то вроде этого. Ф-ция получает указатель на узел и меняет местами его со следующим узлом. Можно, конечно, усовершенствовать, если нужно.

Код: Выделить всё

void cList::SwapToNext(node * pNode)
{
 if(pNode==NULL || pNode==Tail) return;
 node * pPrev=Head;
 while(pNode!=Head && pPrev && pPrev->next!=pNode) pPrev=pPrev->next; // find node befor pNode
 if(pPrev)
 {
  node * p=pNode->next->next;//node after pNode->next
  if(pNode!=Head)
  {
   pPrev->next=pNode->next;
   pNode->next=p;
   pPrev->next->next=pNode;
  }
  else
  {
   Head=pPrev->next;
   Head->next=pNode;
   pPrev->next=p;
  }
 }
}

[rrrFer]

Код: Выделить всё

void List::sort(){
		node *pv,*pt,*pmax,*ptt;
		ptt=new node;
		for(pv=pb;pv;pv=pv->r){
			for(pmax=pt=pv;pt;pt=pt->r)
				if(*pt>*pmax)
					pmax=pt;
			ptt->cpy(*pmax);
			pmax->cpy(*pv);
			pv->cpy(*ptt);
		}
	}

можно так, тут перегружен оператор > для узла (node).
ptt->cpy(*pmax); - данные узла ppt заменяем на данные узла pmax, но ссылки на другие узлы не изменяем.
То-бишь как то так:

Код: Выделить всё

cpy(const node &n){
                info=n.info;
            }