الترتيب الفقاعي على القوائم المتصلة

السلام عليكم ورحمة الله وبركاته,,

الفكرة البسيطة لخوارزمية الترتيب الفقاعي (Bubble Sort) عبارة عن مقارنة كائنين متجاورين، وتبديل مواقعهم إذا كان ترتيبهم خاطئ.

وهنا مثال يوضح تطبيق هذه الخوارزمية على ستة أرقام:

5	10	20	13	7	17
5	10	13	7	17	20
5	10	7	13	17	20
5	7	10	13	17	20	
5	7	10	13	17	20

وهذا الكود يوضح كيفية تطبيق هذه الخوارزمية في لغة السي على المصفوفات:

for (i=0; i<n-1; i++) 
	for (j=0; j<n-1-i; j++) {

		/* مقارنة العددين المتجاورين*/
		if (a[j+1] < a[j]) {	  
			/* تبديل المواقع*/
			tmp = a[j];		 
			a[j] = a[j+1];
			a[j+1] = tmp;
		}
 	}

الكود التالي هو تطبيق هذه الخوارزمية على القوائم المترابطة:

#include <stdio.h>

typedef struct sNode{
	struct sNode *next;
	int info;
}	Node;

Node *bSort(Node *list)
{
	Node *lst, *tmp = list, *prev, *potentialprev = list;
	int idx, idx2, n = 0;

	// تحديد عدد العقد في القائمة 
	for (;tmp->next; tmp=tmp->next)
		n++;

	for (idx=0; idx<n-1; idx++) {
		for (idx2=0,lst=list; lst && lst->next && (idx2<=n-1-idx); idx2++) {

			if (!idx2) 
				prev = lst;

			// مقارنة العقد المتجاورة
			if (lst->next->info < lst->info) {
				// تبديل العقد
				tmp = (lst->next?lst->next->next:0);
				if (!idx2 && (prev == list))
					list = lst->next;

				potentialprev = lst->next;
				prev->next = lst->next;
				lst->next->next = lst;
				lst->next = tmp;
				prev = potentialprev;
			} else {
				lst = lst->next;
				if(idx2)
					prev = prev->next;				 
			}	 
		} 
	}

	return list;
}

int main() {

	Node n1, n2, n3;

	n1.info = 6;
	n1.next = &n2;

	n2.info = 4;
	n2.next = &n3;

	n3.info = 7;
	n3.next = 0;

	Node * result = bSort(&n1);

	while( result ) {
		printf("%d\n", result->info);
		result = result->next;
	}

	getchar();
	return 0;
}

يقوم هذا الكود بتبديل عقدتين في قائمة إذا كانا في ترتيب خاطئ (يقوم بتبديل المؤشرات فقط)، والذي نحتاجه لهذه العملة معرفة العقدة التالية والسابقة للعقد المراد تبديلهم، هذا أعقد شيء في هذه الخوارزمية البسيطة!

بالتوفيق,,