خوارزمية ترتيب الفقاعات (Bubble sort algorithm) (2)

خوارزمية ترتيب الفقاعات (Bubble sort algorithm)

رابط الجزء الأول
كان من المفترض أن نتحدث في هذه المقالة عن خوارزمية الترتيب الثنائي و لكن أحببت أن أبدأ بإحدى خوارزميات الترتيب نظرا لأن الـــ Binary search algorithm يعتمد على فكرة الترتيب.
في هذه المقالة (أو لنقل بقية أجزاء السلسلة) ستجدني أتحدث أحيانا مع شخص افتراضي اسمه عمرو, ألجأ إلى الحديث مع هذا الشخص عندما أصل إلى فقرة تحتاج إلى توضيح أكثر.

-.1.gif 5.83K 20 downloads

في هذا الدرس سنتطرق إلى النقاط التالية :

الخوارزمية (الهدف, الفكرة, النتيجة, الإيجابيات و السلبيات)
قبل أن نبدأ .. إليك 4 طرق لعمل Swap
كتابة دالة تقوم بعملية التبديل
الخوارزمية بلغة السي++
التعقيد الزمني.
ملأ مصفوفة عشوائيا و اختبار سرعة الخوارزمية.

-.1.gif 5.83K 20 downloads

1. الخوارزمية (الهدف, الفكرة, النتيجة, الإيجابيات و السلبيات) :

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

-.1.gif 5.83K 20 downloads

2. قبل أن نبدأ .. إليك 4 طرق لعمل Swap :

من خلال دراستك لخوارزميات الترتيب المختلفة ستجد أن مفهوم Swap أو تبادل مُحتوى متغيرين يتكرر باستمرار .. فأغلب خوارزميات الترتيب (إن لم تكن كلها !) تعتمد في مرحلة ما على تبديل محتوى خانتين لوضعهما في الترتيب الصحيح, لذا سنوضح كيفية تبديل محتوى متغيرين قبل أن نبدأ بكتابة الخوارزمية بلغة السي++.
سنتناول فيما يلي 4 طرق لعمل Swap, لكل منها إيجابيات كما لها سلبيات أيضا.
الطريقة الأولى (و هي الأكثر شهرة) تكمن في استخدام وسيط مساعد يُساعدنا على تبديل محتوى المتغيرين, فنضع قيمة المتغير الأول في الوسيط ثم نضع قيمة المتغير الثاني في المتغير الأول ثم نضع قيمة الوسيط في المتغير الثاني, و بهذا نكون قد بادلنا بين قيمة المتغير الأول و الثاني. لنفرض أن x=5 و y=-1 :
[ltr]t = x //t = 5
x = y //x = -1
y = t //y = 5[/ltr]
في النهاية تكون x=-1 و y=5 . و بالتالي تم تبديل قيمتي x و y.
يمكنك تـخيل الفكرة كما يلي .. لدينا كأسين x و y, الكأس x يحتوي على العصير و الكأس y يحتوي على الماء, لو أردنا أن نُبادل محتوى الكأسين, (أي نجعل الماء في الكأس x و العصير في الكأس y) سنقوم باستخدام كأس ثالث فارغ (وهو الوسيط المساعد t) و تكون عملية التبادل كما يلي :

نجعل العصير في الكأس الفارغ.
نجعل الماء في الكأس x.
نجعل العصير في الكأس y.

الآن أصبح الكأس x يحتوي على الماء و الكأس y يحتوي على العصير. هذه الطريقة بسيطة و تقليدية أيضا, إلا أنها تأخذ مساحة أكثر من الذاكرة بالإعلان عن الوسيط الثالث.
يمكننا عمل Swap بدون حاجة إلى وسيط مساعد عن طريق إجراء بعض العمليات الحسابية البسيطة على المتغيرين.

الطريقة الثانية (تصلح للمتغيرات العددية فقط) :
[ltr]x=x+y;[/ltr]

وان شاء الله ان يعجبكم

خوارزمية ترتيب الفقاعات (Bubble sort algorithm) (2)

خوارزمية ترتيب الفقاعات (Bubble sort algorithm) (2)

رد: خوارزمية ترتيب الفقاعات (Bubble sort algorithm) (2)