خوارزميات الفرز: (الفرز الفقاعي...). Bubble Sort

#119 مارس 2002 في 03:20 صاحب الموضوع

خوارزميات الفرز: (الفرز الفقاعي...).

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

أول ما سنتكلم عنه من خوارزميات الفرز هو خوارزمية الفرز الفقاعي (ترجمة لـ Bubble Sort) أو أي ترجمة أخرى لها، وهذا بالطبع لا يعني أنها أفضل الخوارزميات ولا أنها خوارزمية جيدة إلى حدٍ ما ولكن لا بد من المجيء على ذكرها هنا.

يتلخص أسلوب الخوارزمية بشكل عام (من أجل فرز n عنصراً على سبيل المثال) بالمرور على جميع العناصر n-1 مرة (وليس بالضرورة المرور على جميعها كل مرة -سنرى كيفية ذلك بعد قليل-) ومقارنة كل عنصرين متجاورين فيما إذا كانا في الترتيب الصحيح المراد الفرز وفقه (تصاعدي أو تنازلي لا يهم) والقيام بالمبادلة بينهما في حال اختلال شرط الترتيب.

نكون في مرورنا على جميع العناصر لاول مرة قد ضمنا أننا قد أوصلنا العنصر الاكبر (أو الأصغر) بحسب كوننا نقوم بالفرز تصاعدياً (أو تنازليا) إلى أسفل القائمة لذلك في المرور الثاني لنا على العناصر "يكفي" أن نمر على جميع العناصر باستثناء الأخير (ولا مشكلة إن مررنا على جميع العناصر دوماً ولكن في ذلك إضاعة وقت كبيرة وزيادة في كلفة الخوارزمية). ونكون بذلك قد أوصلنا العنصر الذي يليه إلى الخانة قبل الأخيرة لذلك في المرة الثالثة أيضاً لا داعي للمرور على العنصرين الأخيرين.... وهكذا.

من تسمية الخوارزمية فالعنصر الأكبر في البداية يعةم مثل فقاعة إلى نهاية القائمة فالتالي فالتالي.... ولتكون فكرة الخوارزمية أوضح فهذا مثال (بلغة باسكال) وهي اللغة الأنسب والأقرب إلى لغة الخوارزميات...

يقوم المثال بفرز عناصر مصفوفة (مصقوقة من n عنصراً جميعها أعداد صحيحية على سبيل المثال) ويمكن بالطبع تعميم المسألة على أي نمط معطيات آخر بسيطاً كان أو مركباً (بمقارنة قسم معين من نمط مركب) على أن تسمح لغة البرمجة بمقارنة تلك المعطيات. مثلاً مقارنة String.

في قسم تعريف المعطيات يتم تعريف مصفوفة من n عنصراً (n هو ثابت وليس متحول في باسكال) صحيحاً (من نمط Integer ) أو أي نمط آخر تسمح لك لغة البرمجة بمقارنة عناصره بـ > أو < ، بالإضافة إلى متحول مؤقت من نفس نمط عناصر المصفوفة من أجل المبادلة بين العناصر. ومتحولين من نمط Integer ليكونا عدادين لحلقة المرور على عناصر المصفوفة وتكرار ذلك.

[Code2]

VAR

Table : Array [ 1 .. n ] OF Integer;

Tmp,i,j : Integer;

[/Code2]

أما كود الفرز فهو على النحو التالي (بافترض أنك قمت بإسناد قيم إلى عناصر المصفوفة):

[Code2]

FOR i := 1 TO ( n - 1 ) DO

FOR j := 1 TO (n - i) DO

If Table [ j ] > Table [ j + 1] THEN

Begin

Tmp := Table [ j ];

Table [ j ] := Table [ j +1 ]

Table [ j +1 ] := Tmp

End;

[/Code2]

أرجو أن يكون الكود مفهوماً وواضحاً بالنسبة للجميع حتى للذين لا يعرفون لغة باسكال.

على كل حال يوجد خوارزميات أفضل من هذه الخوارزمية بكثيروسنأتي على ذكرها قريباً إن شاء الله.

على كل حال من الممكن تحسين هذه الخوارزمية قليلاً (قد لا يعتبر ذلك تحسيناً من وجهة نظر أخرى) وذلك إذا كنت تتوقع أن العناصر ستكون مرتبة عند قيامك بترتيبها أو أنها ستكون مرتبة بعد مرورك على جميع العناصر لبضع مرات قليلة (في حالة أنك تضيف عنصراً أكبر إلى القائمة "المرتبة" في بدايتها ) فيكفيك في هذه الحالة المرور مرة واحدة ليكون ذلك العنصر في نهاية القائمة، ولا داعي حيناها للمرورات الأخرى (طبعاً هو مثال لحالة خاصة وكل شخص ممكن أن يرى أموراً أخرى مناسبة حسب طبيعة برنامجه).

وسأذكر مثالاً بسيطاً توضيحاً للفكرة السابقة.

إذا كان لدينا العناصر التالية المرتبة: (1، 2، 3، 4، 5، 6) وأضيف إلى بدايتها العنصر 9 على سبيل المثال فأصبحت: (9، 1، 2، 3، 4، 5، 6) فمن المرور الأول لحلقة المتحول j عليها ستصبح بالشكل (1، 2، 3، 4، 5، 6، 9) ولا داعي أن يأخذ المتحول i قيمه المتبقية الأخرى فتقوم أنت بالخروج حينها من الحلقة ولكن السؤال: كيف؟؟؟

بالإمكان الاستعانة بمتحول منطقي (من نمط Boolean) لتحديد كون العناصر مرتبة في المرور السابق وذلك كما يلي: (المتحول هو SRTD)

[Code2]

Srtd:=False;

FOR i := 1 TO ( n - 1 ) DO

Begin

If Srtd Then Break;

Srtd := True;

FOR j := 1 TO (n - i) DO

If Table [ j ] > Table [ j + 1] THEN

Begin

Tmp := Table [ j ];

Table [ j ] := Table [ j +1 ]

Table [ j +1 ] := Tmp

Srtd:=False;

End;

[/Code2]

قد يحتاج الكود السابق القليل من التوضيح لمن لا يعرفون لغة باسكال:

سيرتبط المتحول المنطقي Srtd بكون حالة العناصر مرتبة عند المرور السابق للحلقة الداخلية (حلقة j ) يُسند للمتحول القيمة False بدايةً كي يتجاوز الشرط If Srtd Then Break; والذي يسبب الخروج من الحلقة الكبيرة (حلقة i) وبالتالي انتهاء الفرز،ثم يسند للمتحول القيمة True قبل دخولنا في الحلقة الداخلية ( j ) فإذا انتهت الحلقة الصغيرة ولم يتم التبديل بين أي عنصرين فهذا يعني أن العناصر مرتبة ولن يفيد أي تكرار لهذه الحلقة وسيحافظ حينها المتحول على القيمة True مما يسبب خروجنا من الحلقة الكبير قبل أن يدخل البرنامج ثانيةً في الحلقة (j) ، وأما إذا تم تبديل مكاني عنصرين مرة واحدة على الأقل فالمتحول سيأخذ القيمة False ولن يتسبب في خروج البرنامج من الحلقة المرة التالي.

هذا الشرط مفيد كما نرى في حال توقعنا لتنفيذ عملية الفرز والعناصر مفروزة بالأصل أما في الحالة العامة في لا يعتبر تحسيناً بل العكس لأنه يتسبب في فحص الشرط والإسناد كل مرة و الإسناد الآخر ضمن الحلقة الضغيرة أيضاً. طبعاً قد يبدو ذلك تافهاً من أجل عناصر قليلة ولكن الفرق يظهر عندما يكون لديك عدد كبير من العناصر فتكرار عملية زائدة (ولو كانت بسيطة) عدداً كبيراً من المرات سيستغرق زمناً ملحوظاً عند استخدام البرنامج.

واعذروني ختاماً على الإطالة!!!

:o :D :D

#219 مارس 2002 في 05:11

وهذا هو الكود بلغة الفيجول بيسك

Dim Table( 1 To n) As Integer
Dim  Tmp As Integer ,I As Integer ,J As Integer

FOR I = 1 TO ( n - 1 ) 
        FOR j = 1 TO (n - I) 
                If Table (  j ) > Table ( j + 1) THEN
                        Tmp = Table (  j )
                        Table (  j ) = Table (  j +1 )
                        Table (  j +1 ) = Tmp
		End If
         Next J
Next I

اللهم أغفر لنا ولوالدينا ومعلمينا وأساتذتنا ومشايخنا وكل من له فضل علينا

إسطوانة كتب كامله فى الرياضيات

عمل تقرير ديناميكى

الكريستل ريبورت وإظهار الصور فى التقرير

الدرس الاول من دروس تعلم DAO بإستخدام الكود

الدرس الثالث من دروس تعلم DAO بإستخدام الكود

الدرس الرابع من دروس تعلم DAO بإستخدام الكود

كيفية إضافة بيانات إلى الملف التنفيذى دون التأثير على عمل الملف

#321 مارس 2002 في 01:31

وهذا الكود بلغة السي طبعاً ستقولون أنه طويل بالنسبه للباسكال

و الفجول بيسك و لكن هذا الكود كود كامل و ليس مقطع الترتيب

فقط.. يعني سوو له كمبايل على طول :D

 
#include < stdio.h >
#define size 6
//---------------------------
void sorting(int [size]);
//---------------------------
main()
{
	int array[size];
	int i;

	printf("nPlease Enter %d numbers to sort: ",size);

	for( i=0 ; i < size ; i++ )
		scanf("%d",&array);
	sorting(array);

	printf("nafter sorting it is: n");
	for( i=0 ; i < size ; i++ )
		printf("%-4d",array);
}
//---------------------------
void sorting(int array[size])
{
	int i, j, temp;

		for( i=0 ; i<(size-1) ; i++ )
			for( j=0 ; j<(size-i) ; j++ )
				if(array[j] > array[j+1] )
				{
					temp = array[j];
					array[j] = array[j+1];
					array[j+1] = temp;
				}
}

مع تحياتي ,,,