bubble sort لیست پیوندی

[rainlover]

سلام به تمامی شما عزیزان.
من الگوریتم تست شده ی bubble sort رو برای لیست پیوندی میخوام اگه کسی میتونه کمکم کنه برای تک پیوندی و دو پیوندی رو برام بذاره.
البته من تا یه جایی نوشتم ولی ایراد داره لا اقل بگید ایرادشو برطرف کنم.
برنامه ای که مشخصات کارمندارو میگیره(نام،شماره کارمند ، حقوق و وضعیت تاهل)باید طبق :ناراحت:شماره کارمندی sort کنه.
من فقط تابع sort رو میذارم.

sort(int count)
{
struct employee *help;
int i,j;
node = first;
for( i=count-1 ; i>0 ; i-- )
for( j=0 ; j<i ; j++ )
{
if(node->empno > node->next->empno && node == first)
{
help = node;
node=node->next;
node->next=help;
first=node;
}
else if(node->empno > node->next->empno)
{
help = node;
node=node->next;
node->next=help;
}
node=node->next;
}
//node -> next = NULL;
}

[emad_67]

برای مرتب سازی لیست پیوندی نمیشه از همون روشی که bubblesort برای اعداد به کار میره استفاده کرد (منظورم گرفتن یک متغیر به عنوان temp و جابجایی اعداد هست) چون توی لیست پیوندی به جای اعداد آدرس ها باید جابجا بشن
به هر حال کدت رو به صورت زیر ، با یه سری تغییرات نوشتم:


void sort(int count)
{
employee*p,*q,*z;
bool flag;
for(int i=0;i<count;i++)
{
p=first;
q=first->next;
z=NULL;
for(int j=0;j<count-1;j++)
{
if((p->empno>q->empno) && p==first)
{
first=p->next;
p->next=q->next;
q->next=p;
flag=1;
}
else if(p->empno>q->empno)
{
z->next=q;
p->next=q->next;
q->next=p;
flag=1;
}
if(flag)
{
z=q;
q=p->next;
}
else
{
z=p;
p=q;
q=q->next;
}
flag=0;
}
}
}

به نظز من اگه مجبور نیستید از bubblesort استفاده کنید میشه در حین وارد کردن متغیر ها در لیست، اون رو سر جای خودش قرار داد که دیگه احتیاجی به sort نباشه.

[*Fatemeh*]

برای مرتب سازی لیست پیوندی نمیشه از همون روشی که bubblesort برای اعداد به کار میره استفاده کرد (منظورم گرفتن یک متغیر به عنوان temp و جابجایی اعداد هست) چون توی لیست پیوندی به جای اعداد آدرس ها باید جابجا بشن
به هر حال کدت رو به صورت زیر ، با یه سری تغییرات نوشتم:


void sort(int count)
{
employee*p,*q,*z;
bool flag;
for(int i=0;i<count;i++)
{
p=first;
q=first->next;
z=NULL;
for(int j=0;j<count-1;j++)
{
if((p->empno>q->empno) && p==first)
{
first=p->next;
p->next=q->next;
q->next=p;
flag=1;
}
else if(p->empno>q->empno)
{
z->next=q;
p->next=q->next;
q->next=p;
flag=1;
}
if(flag)
{
z=q;
q=p->next;
}
else
{
z=p;
p=q;
q=q->next;
}
flag=0;
}
}
}

به نظز من اگه مجبور نیستید از bubblesort استفاده کنید میشه در حین وارد کردن متغیر ها در لیست، اون رو سر جای خودش قرار داد که دیگه احتیاجی به sort نباشه.

میشه درباره ی راهنمایی اخرتون یه کم بیشتر توضیح بدین؟

[rahnema1]

سلام
مرتب سازی حبابی در لیست پیوندی را به سادگی می شه انجام داد البته با این روش مثل روش مرتب سازی آرایه باید کپی انجام بشه که مثلا برای داده هایی که در هر node یک داده سنگین باشه شاید به صرفه نباشه

struct Node
{
int value;
Node* next;
};
void bubble_sort_list(Node* list)
{
for(Node* i = list; i; i = i->next)
{
for(Node* j = i->next; j; j = j->next)
{
if(i->value > j->value)
{
int temp = i->value;
i->value = j->value;
j->value = temp;
}
}
}
}


یه روش دیگه هست که پیوند ها اصلاح میشن:

Node* bubble_sort_list2(Node* list)
{
int counter= 0;
Node* result = 0;
Node* previ = new Node;
Node* prevj = list;
for(Node* i = list; i; i = i->next)
{
prevj = i;
for(Node* j = i->next; j; j = j->next)
{
if(i->value > j->value)
{
prevj->next = i;
previ->next = j;
Node* temp = j->next;
j->next = i->next;
i->next = temp;
temp = i;
i = j;
j = temp;
}
prevj = j;
}
previ = i;
if (counter++ == 0)
result = i;
}
delete previ;
return result;
}

اون جمله آخر که توضیح دادن یعنی هر دفعه که یک فقره داده بخواهد وارد لیست بشه باید از ابتدای لیست پیمایش بشه و هر جا که فقره بعدی از او بزرگتر بود همون جا درج بشه