يساوي7
أهلا وسهلا بك عزيزي الزائر في منتدى يساوي7 للرياضيات
يمكنك التسجيل لدينا من خلال هذه النافذة لتستفيد أكثر من المواضيع المطروحة
وشكرا جزيلا لك

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

استعرض الموضوع السابق استعرض الموضوع التالي اذهب الى الأسفل

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

مُساهمة من طرف محمد جهاد الجبارين في السبت نوفمبر 30, 2013 10:00 am

خوارزمية ترتيب الفقاعات (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]

محمد جهاد الجبارين
عضو متقدم
عضو متقدم

عدد المساهمات : 1448
تاريخ التسجيل : 11/11/2013
العمر : 15
الموقع : الدوارة\سعير \ الخليل
العمل/الترفيه العمل/الترفيه : طالب مجتهد
المزاج المزاج : ممتاز

معاينة صفحة البيانات الشخصي للعضو

الرجوع الى أعلى الصفحة اذهب الى الأسفل

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

مُساهمة من طرف محمد جهاد الجبارين في السبت نوفمبر 30, 2013 12:59 pm

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

محمد جهاد الجبارين
عضو متقدم
عضو متقدم

عدد المساهمات : 1448
تاريخ التسجيل : 11/11/2013
العمر : 15
الموقع : الدوارة\سعير \ الخليل
العمل/الترفيه العمل/الترفيه : طالب مجتهد
المزاج المزاج : ممتاز

معاينة صفحة البيانات الشخصي للعضو

الرجوع الى أعلى الصفحة اذهب الى الأسفل

استعرض الموضوع السابق استعرض الموضوع التالي الرجوع الى أعلى الصفحة

- مواضيع مماثلة

 
صلاحيات هذا المنتدى:
لاتستطيع الرد على المواضيع في هذا المنتدى