مزايا وعيوب فرز الفقاعات

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

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

أثناء المبادلة = المبادلة الحقيقية = خطأ لـ i = 0 إلى tbl.length - 2 إذا كان tbl (i)> tbl (i + 1) ثم tmp = tbl (i) tbl (i) = tbl (i + 1) tbl (i + 1) = tmp swap = True End If Next End while

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

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

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