خوارزم الفقاعة للترتيب Bubble Sort Algorithm

Spread the love

خوارزم الفقاعة للترتيب Bubble Sort Algorithm

(بواسطة : رسيــــس | بتاريخ : 10 أغسطس 2004 )

بسم الله الرحمن الرحيم

خوارزم الفقاعة للترتيب Bubble Sort Algorithm

يعتبر هذا الخوارزم يعتبر الأبطأ من بين أقرانه، حيث يقوم هذا الخوارزم بترتيب عناصر المصفوفة عنصراً عنصراً عن طريق مقارنته بالعنصر الذي بعده، ويقوم بالتبديل في موقعهما في المصفوفة متى ما استلزم الأمر. يكرر هذا الخوارزم هذه الدورة على جميع العناصر عنصراً خلف الآخر إلى أن يصل إلى دورة لا يتغير فيها موقع أي عنصر، حينها يتوقف وتكون العناصر قد ترتبت!

بعبارة أخرى:
يعمل هذا الخوارزم على ترتيب عناصر مصفوفة ليست مرتبة العناصر، وتتم عملية الترتيب على مراحل أو دورات phases كل مرحلة تتضمن عملية مقارنة زوجين متجاورين من العناصر واستبدال موضعهما إذا كان ترتيبهما غير صحيح… وهكذا، انظر إلى الرسم:

 

مثال:

لنفرض أننا نريد ترتيب مصفوفة تحتوي س من العناصر تصاعدياً، بعد دورته الأولى في المصفوفة سيكون أكبر عنصرموضوع في مكانه الصحيح (آخر المصفوفة بمعنى [س-1])، وبعد دورته الثانية سيكون ثاني أكبر عنصر في المصفوفة في مكانه الصحيح ([س-2])، ……..وهكذا، يتوقف الخوارزم متى ما أتم دورة دون تبديل في أماكن العناصر.
تقلب الآية لو كان الترتيب تنازلياً.

والآن قد تتساءل كيف نكتب هذا الكود برمجياً؟!

الإجابة سهلة، يمكنك تمثيل الخوارزم السابق بأي لغة برمجة تتقنها، وهذا هو الكود المستخدم في برنامج “خوارزميات الترتيب” الذي حملّته من درس المقدمة:

// array of integers to hold values
private int[] a = new int[100];

// number of elements in array
private int x;

// Bubble Sort Algorithm
public void sortArray()
{
int i;
int j;
int temp;

for( i = (x – 1); i >= 0; i– )
{
for( j = 1; j <= i; j++ )
{
if( a[j-1] > a[j] )
{
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
}
}

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

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::2

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::3

::__IHACKLOG_REMOTE_IMAGE_AUTODOWN_BLOCK__::5

من المؤكد أنك لاحظت بإن المصفوفة ترتبت بعد الدورة الرابعة، لكن الخوارزم أكمل حتى الدورة الثامنة ولم يتوقف فوراً، هذا صحيح، لذلك تعتبر هذه الطريقة من أبسط وأبطأ طرق الترتيب!

ربما تتسآءل منذ البدايو لماذا هذا الاسم الغريب، نعن هاأنت قد عرفت الآن بعد أن رأيت طريقة الترتيب وخطواتها في البرنامج، سميت بالفقاعة لأن العنصر الأصغر يصعد كالفقاعة إلى بداية المصفوفة 🙂

معلومة إضافية متقدمة:

لو استخدمنا مفهوم Big-Oh Notation لتحليل هذا الخوارزم لاستنتجنا أن أسوأ حالات تطبيق هذا الخوارزم هي عندما يكون (O(n2 وهو نفسه درجة فعالية هذا الخوارزم في الحالة القياسية.

 

الكاتب geek4arab

geek4arab

مواضيع متعلقة

التعليقات مغلقة