برنامج C لفرز الفقاعات: فرز الفقاعات في C.

مقدمة

يحتل فرز المصفوفة أهمية كبيرة في علوم الكمبيوتر. يتم ملاحظة فائدتها عندما تكون هناك حاجة لترتيب البيانات بترتيب معين. هناك أنواع مختلفة من خوارزميات الفرز. خوارزمية الفرز الأكثر شيوعًا والأكثر استخدامًا هي Bubble Sort.

فرز الفقاعات في C.

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

هذه الخوارزمية قابلة للمقارنة مع الفقاعات في الماء لأنها تقوم بتصفية الجزء العلوي من الفقاعات الشبيهة بالصفيف. من بين جميع الخوارزميات المستخدمة للفرز ، يعتبر فرز الفقاعات أسهل وأبطأ مع تعقيد زمني لـ O (n ^ 2). ومع ذلك ، يمكن تحسين الخوارزمية من خلال استخدام متغير إشارة يخرج من الحلقة عند اكتمال التبديل. يمكن أن تكون أفضل حالة لفرز الفقاعة هي O (n) عند فرز المصفوفة.

على سبيل المثال ، دعنا نأخذ مصفوفة لم يتم فرزها من خمسة أرقام كما هو موضح أدناه

13 ، 32 ، 26 ، 34 ، 9

سيبدأ فرز الفقاعة في التفكير في العنصرين الأولين ، وسوف يقارنانهما للتحقق من أيهما أكبر. في هذه الحالة ، 32 أكبر من 13. إذن هذا الجزء مصنف بالفعل في y. بعد ذلك ، نقارن 32 بـ 26. إذن نجد أن 32 أكبر من 26 ، لذلك يجب تبديلهما. ستبدو المصفوفة الجديدة

13 ، 26 ، 32 ، 34 ، 9

بعد ذلك ، نقارن 32 و 34. نحن نعلم أنهما تم فرزهما بالفعل. وهكذا ننتقل إلى المتغيرين الأخيرين 34 و 9. نظرًا لأن 34 أكبر من 9 ، فيجب تبديلهما.

نتبادل القيم ونصل إلى نهاية المصفوفة بعد التكرار الأول. الآن سوف تبدو المصفوفة

13 ، 26. 32،9،34

بعد التكرار الثاني ، ستبدو المصفوفة

13 ، 26 ، 9 ، 32 ، 34

بعد التكرار الثالث ، ستصبح المصفوفة

13،9،26،32،34

بعد التكرار الرابع ، سيتم فرز المصفوفة بالكامل

9 ، 13 ، 26 ، 32 ، 34

يجب أن تقرأ: أفكار المشروع في C

الخوارزمية

نحن هنا نفترض أن المصفوفة تحتوي على عدد n من العناصر. علاوة على ذلك ، نفترض أن وظيفة قيم التبادل تقوم بتبديل جميع القيم لجعل أرقام الصفيف في ترتيب مرتبة.

بدء BubbleSort (مجموعة)

لجميع عناصر القائمة

إذا كانت المصفوفة [i]> مجموعة [i + 1]

قيم التبادل (صفيف [i] ، صفيف [i + 1])

إنهاء إذا

نهاية ل

مجموعة العودة

فرز الفقاعة النهائية

قراءة: الفرز في بنية البيانات: الفئات والأنواع

كود مزيف

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

يمكن كتابة الكود الزائف لخوارزمية BubbleSort على النحو التالي

إجراء BubbleSort (مجموعة: عناصر في المصفوفة)

كرر = array.count ؛

من أجل k = 0 للتكرار -1 افعل:

العلم = خطأ

من أجل l = 0 للتكرار -1 افعل:

إذا (مجموعة [ل]> مجموعة [ل + 1]) ثم

قيم التبادل (صفيف [l] ، صفيف [l + 1])

العلم = صحيح

إنهاء إذا

نهاية ل

إذا (لم يتم تبديلها) إذن

استراحة

إنهاء إذا

نهاية لـ

نهاية الإجراء إرجاع مجموعة

دعونا نجرب عينة من برنامج فرز الفقاعات في C :

# تشمل <stdio.h>

الرئيسية باطلة

{

مجموعة int [10] ، i ، j ، الأسطوانات

لـ (i = 0 ؛ i <= 9 ؛ i ++)

{

مسح ضوئي ("٪ d" ، & صفيف [i])

}

لـ (i = 0 ؛ i <= 9 ؛ i ++)

{

لـ (j = 0 ؛ j <= 9-i ؛ j ++)

{

إذا (مجموعة [ي]> مجموعة [ي + 1])

{

عدد = مجموعة [ي] ؛

صفيف [j] = صفيف [j + 1] ؛

الصفيف [j + 1] = الأسطوانات ؛

}

}

}

printf ("المصفوفة المرتبة / n") ؛

لـ (i = 0 ؛ i <= 9 ؛ i ++)

{

printf ("٪ d"، & صفيف [i])

}

}

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

هناك حلقة أخرى داخل الحلقة الخارجية. يبدأ من j = 0 ويستمر حتى يصبح أصغر من ثمانية أو يساوي. في الداخل ، هناك عبارة if شرطية تقارن وتتحقق مما إذا كانت المصفوفة [j] أكبر من المصفوفة [j + 1]. إذا تم استيفاء الشرط ، يتم تبديل قيم المصفوفة [j] والمصفوفة [j + 1] مع بعضها البعض.

يتم استخدام متغير باسم num لهذا الغرض. المصفوفة الأولى [j] تُسند إلى num ، ثم المصفوفة [j + 1] تُسند إلى المصفوفة [j] ، وأخيراً تُسند num إلى المصفوفة [j + 1]. ستستمر هذه العملية حتى يتم فرز جميع العناصر في المصفوفة بترتيب تصاعدي. بعد ذلك ، يتم طباعة المصفوفة التي تم فرزها.

التنفيذ الأمثل لفرز الفقاعات

لدينا خوارزمية محسنة لفرز الفقاعات لتحسين النتائج. استخدام متغير العلم هو الأمثل. سيحتفظ متغير العلم بـ 1 إذا كان هناك مبادلة وإلا فسيخرج من الحلقة. يوجد أدناه برنامج فرز الفقاعات المحسن في C.

# تضمين <stdio.h>

الرئيسية باطلة

{

مجموعة int [10] ، i ، j ، num ، flag = 0 ؛

لـ (i = 0 ؛ i <= 9 ؛ i ++)

{

مسح ضوئي ("٪ d" ، & صفيف [i])

}

لـ (i = 0 ؛ i <= 9 ؛ i ++)

{

لـ (j = 0 ؛ j <= 9-i ؛ j ++)

{

إذا (مجموعة [ي]> مجموعة [ي + 1])

{

عدد = مجموعة [ي] ؛

صفيف [j] = صفيف [j + 1] ؛

الصفيف [j + 1] = الأسطوانات ؛

العلم = 1 ؛

}

إذا (! علم)

{

استراحة؛

}

}

}

printf ("المصفوفة المرتبة / n") ؛

لـ (i = 0 ؛ i <= 9 ؛ i ++)

{

printf ("٪ d"، & صفيف [i])

}

}

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

تعقيد الوقت

أفضل تعقيد زمني لفرز الفقاعة هو O (n). يحدث ذلك عندما يتم فرز المصفوفة بالفعل. أسوأ حالة هي O (n * n) عندما لا يتم فرز المصفوفة.

اقرأ: أفضل 12 برنامجًا للنماذج في Java يجب عليك التحقق منها اليوم

ماذا بعد؟

إذا كنت مهتمًا بمعرفة المزيد حول Java ، وتطوير البرامج المتكاملة ، فراجع دبلوم PG upGrad & IIIT-B في تطوير البرامج الكامل المكدس المصمم للمهنيين العاملين ويقدم أكثر من 500 ساعة من التدريب الصارم ، وأكثر من 9 مشاريع ، والمهام ، وحالة خريجي IIIT-B ، ومشاريع التخرج العملية العملية والمساعدة في العمل مع الشركات الكبرى.