خوارزمية ال Bubble Sort

المقدمة :

من بين الأمور التي تشدني دوما هي العمل على حل الخوارزميات و أريد من خلال هذا الدرس اوالمقال البسيط ان أعطيكم شرح مبسط لخوارزمية مشهورة يمكن ان تكونوا قد استعملتموها دون معرفة اسمها او تعرفونها تمام المعرفة وطبعا قد تكون هذه أول مرة تصطدمون بها، الخوارزمية التي ساعرض شرحها اليوم تسمى ال Bubble Sort و كما يظهر من اسمها فهي خوارزمية للترتيب.

شرح للخوارزمية

لنفرض لدينا مصفوفة معينة من نوع Integer تحتوي على عدة أرقام غير مرتبة و نريد ان نكتب كود يقوم بترتيب الأرقام في المصفوفة من الأصغر الى الأكبر مثلا، طبعا قد يتبادر لذهن بعض مبرمجي الدوت نت استعمال الدالة Sort التابعة للمصفوفات بكل بساطة و التخلص من كل التعقيدات و على ذكر هذا الأمر فهذا من مساوء الدوت نت و التسهيلات التي فيه حيث ان المبرمج اصبح لاغيا لعقله لدرجة لا تصدق فكل شئ يمكن عمله بأقل جهد و هذا ينفع في أمور لكنه رغم ذلك سئ و رغم اني مبرمج دوت نت الا أني أقول هذا الكلام فقط لاحقاق الحق، المهم نحن هنا لا نريد استعمال هذه الدالة و لا غيرها لكننا نريد استعمال خورزمية يمكننا تنفيذها باي لغة برمجة(طبعا المثال هنا سيكون بالفيجوال دوت نت) لذا لن نخرج على نطاق الحلقات التكرارية و الجمل الشرطية …
اذا دعونا نضع مثال للمصفوفة :

6 3 5 1 12 15
5 4 3 2 1 0

طبعا هنا عملت مثال مصفوفة صغير الحجم من ست خانات و كما هو في الرسم فالسطر العلوي للقيم و السفلي لرقم الخانة مثلا الخانة 3 من المصفوفة قيمتها هي 5 الآن هدفنا ترتيب الأرقام للحصول على الشكل التالي :

 

15 12 6 5 3 1
5 4 3 2 1 0

قبل ان أبدأ الشرح حاول أن تجد الحل لذا ضع ورقة و قلم امامك و اعمل لايجاد حل خاص بك قبل ان تقرأ طريقة الخوارزمية Bubble Sort و انا متأكد انك لو اتبعت المنطق فلن تفشل باذن الله.

قبل كتابة أي سطر للخوارزمية دعوني أشرح كيفية عملها نظريا كل ما علينا فعله هو ان نأخذ رقمين ثم نقارنهما و هذين الرقمين سنمثلهما ب I و I+1 نقوم بالمقارنة التالية I>I+1 فاذا كانت نتيجتها صحيحة أي أن I أكبر قطعا من I+1 نقوم بتديل القيم حيث ان I=I+1 و I+1 = I و نتابع الى أن نجد انه لا تبديل للقيم ممكن وفي هذه الحالة تكون المصفوفة قد رتبت بشكل جيد، أتمنى أن يكون هذا الشرح النظري قد أوصل اليك الفكرة لكن لا تخف فلسوف نقوم بكتابة الكود و شرحه سطر سطر اذا كانت قد اختلطت عليك الأمور في هذا الشرح.

شرح الكود

الآن سأضع الكود الخاص بالخوارزمية و ستلاحظ بعد نهايتك من قراءة المقال أن الأمر جد بسيط :

Dim MyArray(6) As Integer
Dim Permut As Boolean

MyArray(0) = 15
MyArray(1) = 12
MyArray(2) = 1
MyArray(3) = 5
MyArray(4) = 3
yArray(5) = 6

Do
Permut = False

For i = 0 To UBound(MyArray) – 1
If MyArray(i) > MyArray(i + 1) Then
Permutation MyArray(i), MyArray(i + 1)
Permut = True
End If
Next

Loop While Permut = True

و نضيف كود ال Permutation

Public Function Permutation(ByRef X As Integer, ByRef Y As Integer)
Dim Tmp As Integer
Tmp = X
X = Y
Y = Tmp
End Function

الآن سوف نشرح الكود الأول سطرا سطرا :

السطر رقم 1
تعرف المصفوفة و عدد خاناتها 6 كما في المثال الذي ذكرته سابقا

السطر رقم 2
تعريف متغير من نوع Boolean  و سيكون هو الذي سيحدد اذا ماكنا سنستمر في الحلقة ام نتوقف و نخرج منها و سوف يظهر ذلك لاحقا.

السطر رقم 4-9:
ملأ المصفوفة بالأرقام مثل تلك التي ذكرت في المثال.

السطر رقم 12 :
بداية الحلقة التكرارية While

السطر رقم 14 :
إعطاء المتغير Permut  القيمة الافتراضية و هي False  بمعنى أنه لا توجد تبديلات أنجزت.

السطر رقم 16 :
بداية الحلقة التكرارية FOR  و التي هنا ستبدأ من 0 أي الخانة الأولى للمصفوفة الى Ubound(MyArray)-1 بمعنى N-1 و ذلك لأننا كما ذكرنا دوما سنقوم بمقارنة الخانة I  مع الخانة I+1 لذا لو وصلنا الى آخر خانة و هي 5 سيحدث خطا لأنه سيقرانها مع الخانة I+1 و ستكون 6 و هي غير موجودة لذا ننقص واحد ليكون الحد هو المقارنة بين الخانة 4 و الخانة 5

السطر رقم 18 :
هنا كما تلاحظون المقارنة بين الخانة I   و الخانة I+1  و طبعا لا أظن ان هذا السطر يحتاج شرح فالمقارنة فقط لمعرفة الرقم الأكبر.

السطر رقم 20 :
هنا اذا تحقق الشرط السابق نقوم بعمل التبديل عن طريق دالة كتبناها و اسمها Permutation  تستقبل متغيرين و تقوم بوضع قيمة المتغير الأول في الثاني و الثاني في الأول و سوف نشرح كود هذه الدالة لاحقا.

السطر رقم  21 :
هنا نغير قيمة المتغير Permut  الى True  بمعنى انه تم هناك تبديل وطبعا اذا خرجنا من الحلقة دون ان تتغير قيمة ال Permut  بقيت False  قهذا يعني انه لم يحدث أي تبديل و بمعنى اصح ان المصفوفة مرتبة فنخرج من الحلقة الكبيرة و في While  و سوف نرى ذلك.

السطر رقم 23 :
نهاية الجملة الشرطية.

السطر رقم 25 :
نهاية الحلقة التكرارية FOR

السطر رقم 27 :
نهاية الحلقة While
و في هذه النهاية نتأكد من ان المتغير Permut  له القيمة True  فلو كانت كذلك نتابع الحلقة و الا فسنتوقف اذا كان العكس.

الآن ننتقل لشرح كود دالة التبديل Permutation

Public Function Permutation(ByRef X As Integer, ByRef Y As Integer)
Dim Tmp As Integer
Tmp = X
X = Y
Y = Tmp
End Function

هنا الدالة تستقبل متغيرين X  و Y  و طريقة الاستقبال مختلفة حيث انه تسبقهما كلمة ByRef  و من أجل فهم هذه الكلمة و منافعها بل و شرك وافي لهذه الدالة المرجو الاطلاع على موضوع : الفرق بين ByRef و ByVal.

أتمنى أن يكون المقال مفيد لكم و لو كانت لديكم أية اسئلة فانا تحت أمركم
و السلام عليكم

اضف تعليقا

أيوب جمال الادريسي

جميع الدروس