Adaptivity
الدرس 6 من 11 في دورة الفرز الفقاعي (Bubble Sort) على Coddy.
لقد ناقشنا التعقيد الزمني لخوارزمية فرز الفقاعة (bubble sort)، وهو O(n2). ولكن، ماذا لو كانت المصفوفة مرتبة بالفعل؟ حينها أيضاً، ستستغرق وقت تشغيل قدره O(n2).
ما هي التكيفية (Adaptivity)؟
الخوارزمية التكيفية هي خوارزمية تغير سلوكها بناءً على تسلسل المدخلات المعطى.
إذاً، هل فرز الفقاعة تكيفي؟
نعم، يمكننا جعل خوارزمية فرز الفقاعة تكيفية. يتعين علينا كتابة خوارزمية فرز الفقاعة بحيث يكون وقت التشغيل في أسوأ حالة هو O(n2) وفي أفضل حالة هو O(n) لكي تصبح تكيفية. هنا، تشير أفضل حالة إلى الحالة التي تكون فيها المصفوفة مرتبة بالفعل.
سنستخدم متغير علامة منطقي (boolean flag) للتحكم في حلقة while بحيث تتوقف الخوارزمية مبكراً إذا تم فرز المصفوفة من قبل.
while(flag)
{
//code
}
علينا تكرار التمريرة (pass) حتى يتم فرز المصفوفة. لقد تعلمنا بالفعل كيفية حساب عدد عمليات التبديل (swaps)، لذا يمكننا تنفيذ علامة (flag) والتحقق مما إذا لم تكن هناك حاجة لأي تبديل في التمريرة، ومن ثم يمكننا كسر الحلقة.
التحدي
متوسطقم بإنشاء دالة باسم ad_bubblesort تستقبل مصفوفة وحجم المصفوفة. قم بتنفيذ خوارزمية فرز الفقاعات التكيفي (adaptive bubble sort). تذكر استخدام متغير باسم flag للتحقق من عمليات التبديل.
جرّب بنفسك
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// اكتب الكود هنا
*returnSize = n;
return arr;
}
جميع دروس الفرز الفقاعي (Bubble Sort)
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm