الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

خوارزمية الترتيب الفقاعي .. وتعقيدها الزمني ...

بدأه سنان محمد صالح في 26 يناير 2008 · 9 رد · 11,477 مشاهدة · في المواضيع والدروس
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

السلام عليكم اخوان ..

اغلبكم يعرف ماهي خوارزمية التريب الفقاعي ..

وللذي لا يعرف ماهي خوارزمية الترتيب الفقاعي .. هي خوارزمية تستعمل لترتيب عناصر اما بشكل تصاعدي او تنازلي ..

وغالبا ما تستعمل مع المصفوفات لغرض ترتيب عناصرها تصاعديا او تنازليا...

الخوارزمية توضح بالكود التالي .. 

So you would fill Grades(5) with the values. Then you would say -

for ctr = 1 to 4
.for ctr2 = ctr + 1 to 5
..if Grades(ctr) < Grades(ctr2) then
...Temp = Grades(ctr)
...Grades(ctr) = Grades(ctr2)
...Grades(ctr2) = Temp
..end if
.next
next

ولتمثيلها بلغة السي ++ .. نستخدم الكود التالي ..

for(int x=0; x<n; x++)

	{

		for(int y=0; y<n-1; y++)

		{

			if(array[y]>array[y+1])

			{

				int temp = array[y+1];

				array[y+1] = array[y];

				array[y] = temp;

			}

		}

	}

عن طريق الكود يمكن تحديد TIME COMPLEXITY الخاص بهذه الخوارزمية وهو سيكون O(N^2) اي انها تربيعيه ..

ويمكن اثبات ذلك بشيئين .. الاول .. ان الكود يحتوي على loop في داخل loop اخرى وهذا يجعل n الداخليه تضرب مع n الخارجيه لتصبح n^2

الاثبات الثاني ..

قانون زمن هذه الداله هو 1.5N^2 - 0.5N .. ومنه O(N^2) ..

هذا ما اكتشفته في يدي .. وما تأكدت منه بعد ذلك من مواقع الانترنيت ..

ولكن وجدت شخص (لا اريد ان اذكر ماهو بالنسبه الي) يقول بان زمن هذه الخوارزمية من نوع N log N .. والسبب في ذلك هو ان الدوارة الداخليه والخارجيه تكون في بعض الاحيان على اختلاف فتقل واحد وتزداد الاخرى فتحقق شرط الزمن اللوغارتمي وليس التربيعي ..

فجعلني اشك في معلوماتي ..

فلذلك ها انا اضع المعلومات بين ايديكم .. واضع المشكله .. واضع حلي ايضا لكم .. فما هو الزمن الصحيح للخوارزمية وكيف استنتجتم ذلك .؟؟

تحياتي العطرة وانتظر اجابتكم على السؤال ..

1

يَارَبُ إِن ضَاقَت قُلُوُب الْنَّاسٍ عَنْ مّافِي .. مِنْ خَيْرٍٍ فَعَفْوكَ لَا يَضِيْقْ ..

#2

السلام عليكم أخ سنان,

بالنسبة لتعقيد الخوارزمية فهو في أسوأ حالة :

O(n²)

أي عندما نريد ترتيب المصفوفة تصاعدياً و هي مرتبة اصلاً تنازلياً ,,

طبعاً الوقت المطلوب لترتيب العناصر سيقل كلما كانت المصفوفة مرتبة جزئياً,

تحياتي ,,

2
#3

نفس كلام الأخ خالد لكن كود السي الذي كتبته به خطأ لأنك وبكل بساطة لم تستخدم المتغير x أصلا

من أقوال الأئمة

الإمام علي بن أبي طالب -رضي الله عنه-: "الناس ثلاثة : فعالم رباني ، ومتعلم على سبيل النجاة ، وهمج رِعاع غوغاء أتباع كل ناعق ، يميلون مع كل ريح ، لم يستضيئوا بنور العلم ، ولم يلجئوا إلى ركن وثيق".

الإمام مالك -رحمه الله- : " لن يصلح آخر هذه الأمة إلا بما أصلح به أولها ".

الإمام الأوزاعي -رحمه الله- : " عليك بآثار من سلف وإن رفضك الناس وإياك وآراء الرجال وإن زخرفوه لك بالقول ".

الإمام الفضيل بن عياض -رحمه الله- : " عليك بطرق الهدى و لا يضرك قلة السالكين و إياك و طرق الضلالة ولا يغرك كثرة الهالكين ".

علامة الزمان الإمام الألباني -رحمه الله- : " إن الخلاص إلى أيدي هؤلاء الشباب يتمثل في أمرين لا ثالث لهما ؛ التصفية والتربية ".

وكل خير في اتباع من سلف وكل شر في ابتداع من خلف

#4

بالطبع ..

في اسوأ الاحوال .. فان التعقيد الزمني الخاص بخوارزمية الترتيب الفقاعي هو N^2 ....

ولكن لماذا انتم بالذات الذين رددتم على الموضوع .. اردت ان اجعل بقية الاعضاء هم من يردون عليه ..

اقتباس
لكن كود السي الذي كتبته به خطأ لأنك وبكل بساطة لم تستخدم المتغير x أصلا

اخي باسم .. فائدة المتغير x فقط لتكرر دوارة الy .. فكل x يمثل العنصر الذي نريد ان نختبره .. فهو يعبر عنه ولا يستعمل لهذا الاجل ..

تحياتي العطرة ...

يَارَبُ إِن ضَاقَت قُلُوُب الْنَّاسٍ عَنْ مّافِي .. مِنْ خَيْرٍٍ فَعَفْوكَ لَا يَضِيْقْ ..

#5

لمصفوفة أحادية:

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>

void matrixSort(int *, int);
void swap (int *,int *);

int main()
{
	int Matrix[10];

	cout<<"Matrix[10], has the following elemnts:"<<endl;

	for(int i = 0; i < 10; i++)
	{
		Matrix = 1 + rand() % 100;
	}

	for(i = 0; i < 10; i++)
	{
		cout<<"["<<Matrix<<"]"<<setw(2);
	}

	cout<<endl<<"Your matrix after sorting: "<<endl;
	matrixSort(Matrix,10);

	for(i = 0; i < 10; i++)
	{
		cout<<"["<<Matrix<<"]"<<setw(2);
	}

	cout<<endl;

	return 0;

}

void matrixSort(int *array,int size)
{
	for(int i = 0; i < size; i++)
	{
		for(int j = 0; j < size-1; j++)
		{
			if(array[j] > array[j+1])
				swap(&array[j],&array[j+1]);
		}
	}

}

void swap (int *element1,int *element2)
{
	int temp;
	temp = *element1;
	*element1 = *element2;
	*element2 = temp;
}

لمصفوفة ثنائية:

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>

void convertToArray(int);
void matrixSort(int *,int);
void swap (int *,int *);
int convertToMatrix();
int arrayValue();

int array[100];
int matrix[10][10];

int main()
{

	for(int i = 0; i < 10; i++)
	{
		for(int j = 0; j < 10; j++)
		{
			matrix[j] = 1 + rand() % 9;
		}
	}

	cout<<"Matrix[10][10], has the following elemnts:"<<endl;

	for(i = 0; i < 10; i++)
	{
		for(int j = 0; j < 10; j++)
		{
			cout<<"["<<matrix[j]<<"]"<<setw(2);
		}
		cout<<endl;
	}


	for(i = 0; i < 10; i++)
	{
		for(int j = 0; j < 10; j++)
		{
			int holder;
			holder = matrix[j];
			convertToArray(holder);
		}
	}

	cout<<endl;

	matrixSort(array,100);

	for(i = 0; i < 10; i++)
	{
		for(int j = 0; j < 10; j++)
		{
			matrix[j] = convertToMatrix();

		}
	}

	cout<<endl<<"Your matrix after sorting: "<<endl;

	for(i = 0; i < 10; i++)
	{
		for(int j = 0; j < 10; j++)
		{
			cout<<"["<<matrix[j]<<"]"<<setw(2);
		}
		cout<<endl;
	}


	cout<<endl;
	cout<<endl;

	return 0;

}

void convertToArray(int x)
{
	static int i = 0;
	array = x;
	i++;
}

void matrixSort(int *array,int size)
{
	for(int i = 0; i < size; i++)
	{
		for(int j = 0; j < size-1; j++)
		{
			if(array[j] > array[j+1])
				swap(&array[j],&array[j+1]);
		}
	}

}

void swap (int *element1,int *element2)
{
	int temp;
	temp = *element1;
	*element1 = *element2;
	*element2 = temp;
}

int convertToMatrix()
{
	int static i = 0;
	int holder;
	holder = array;
	i++;

	return holder;

}

الفكرة هون انو تحول المصفوفة من ثنائية لأحادية بعدين ترتب العناصر و ترجع تحول من أحادي لثنائي.

تم تعديل هذه المشاركة بواسطة da666ni في 27 مارس 2008 في 19:02

Chao!!!

Great place, and people, but full of sectarianism.

#6

ما شاء موضوع جميل

درستها فى الجامعة و لكن على ورق فقط :lol:

00020309t.gif

1958_1963.gif
#7

عندي مبادئ بسيطة في الخوارزميات .. و على حسب معرفة قليلة جدا ً :

أعتقد أن الـ LOOP الداخلية محققة دائما ً

لذلك ليس للتعقيد هنا worst time أو best time لآنه ليس هناك continue أو break مثل خوارزمية الترتيب السريع أو الترتيب بالدمج

#8

على فكرة كان من الممكن أن تقلل من تكرار الحلقة الداخلية فتصبح

 for(int y=0; y<n-1-x; y++)

لآن كل العناصر التي ما قبلها ستكون مرتبة حكما ً

تم تعديل هذه المشاركة بواسطة aohammed في 16 يوليو 2010 في 11:13

#9

حساب بسيط باستخدام الجبر

لنفترض ان عدد العناصر N

الحلقة الداخلية ستنفذ هكذا

N+(N-1)+(N-2)+(N-3)........+1 وباسستخدام قانون جاوس هتساوي N(N+1)/2 وباهمال الحد الاصغر نجد انه يساوي N^2

1 −1
#10

انا بتفق مع aohammed

لا يمكن اعتبار ان هناك فعلا Worst-Case, Average-Case Nor Best Case Scenario

لأن زمن تنفيذ الخوارزم يعتمد على عدد العناصر n بصفه أساسيه ولا يعتمد جقا على العناصر نفسها أو ترتيبها على عكس خوارزميات اخرى ك Insertion Sort الذي يعمل بكفاءه كبيره اذا كانت العناصر مرتبه فعلا الى حد كبير لكنه في أسوأ الحالات O(n ^ 2)

هناك خوارزميات ترتيب اخرى تعمل في زمن O(n lg n) كال Merge Sort

كما ان هناك خوارزميات ترتيب تعمل في Linear Time فتعتبر O(n) و ذلك تحت بعض القيود فهذه الخوارزميات لا تعتمد على المقارنه لترتيب العناصر :)

1

مواضيع مشابهة