Stability

في هذا الدرس، سنتحقق من الطبيعة المستقرة لخوارزمية فرز الفقاعة (bubble sort).

ما هو الاستقرار؟

يُقال إن خوارزمية الفرز مستقرة إذا ظهر كائنان لهما مفاتيح متساوية بنفس الترتيب في المخرجات المصنفة كما يظهران في المصفوفة المدخلة المراد فرزها.

على سبيل المثال، إذا كان علينا فرز المصفوفة - [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] ، فلدينا هنا رقمان 8، يرمز لهما بـ 8₁ و 8₂. بعد الفرز، يمكن الحصول على مصفوفتين محتملتين - [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>] و [1,2,4,6,<strong>8<sub>2</sub></strong>,<strong>8<sub>1</sub></strong>] . كلتا المصفوفتين مصنفتان، ولكن في المصفوفة الثانية، يختلف ترتيب الرقمين 8، بينما في المصفوفة الأولى، هو نفسه كما في المصفوفة المدخلة.

الآن، دعونا نتحقق من ذلك بالنسبة لخوارزمية فرز الفقاعة.

التمريرة الأولى: [2,<strong>8<sub>1</sub></strong>,4,<strong>8<sub>2</sub></strong>,6,1] -> [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>]

التمريرة الثانية: [2,4,<strong>8<sub>1</sub></strong>,6,1,<strong>8<sub>2</sub></strong>] -> [2,4,6,1,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

بعد كل التمريرات، ستكون النتيجة النهائية: [1,2,4,6,<strong>8<sub>1</sub></strong>,<strong>8<sub>2</sub></strong>]

حاول أن تلاحظ أن ترتيب الرقمين 8 هو نفسه في كل من مصفوفات المخرجات والمدخلات.

وبالتالي، فإن خوارزمية فرز الفقاعة مستقرة!