منتدي لمناقشه الموضوعات الجامعيه.


    الترتيب بالادخال

    شاطر

    Admin
    المدير العام
    المدير العام

    المساهمات : 81
    تاريخ التسجيل : 13/04/2010

    الترتيب بالادخال

    مُساهمة  Admin في الثلاثاء أبريل 13, 2010 11:02 am

    <div align="center">خوارزمية الترتيب بالإدخال(أو الحشر)
    insertion sort algorithm
    </div>


    إذا فهمت فكرة أي خوارزمية، فِإنه يمكن تطبيقها تبعاً لذلك على أي لغة برمجية ، سأحاول بحول الله أن أقدم فكرة مجردة
    عن كيفية تطبيق خوارزمية الترتيب بالإدخال..Abstract idea


    لنفترض أن لدينا المصفوفة ذات البعد الواحد التالية..
    One dimension array
    8 1 7 2 4
    إن المصفوفات هي نوع من أنواع القوائم lists
    والتي يمكن أن نطبق عليها إحدى خوارزميات الترتيب، ومنها خوارزمية الترتيب بالإدخال أو الحشر
    Insertion sort


    * تتكون هذه المصفوفة من 5 عناصر غير مرتبة لا تصاعدياً ولا تنازلياً
    * سنقوم بمحاولة ترتيب هذه المصفوفة تصاعدياً ( من الأصغر إلى الأكبر )
    باستخدام خوارزمية الترتيب بالإدخال كما يلي :

    سنبدأ من اليسار إلى اليمين في الترتيب ، بحكم أنها مصفوفة ، فالبداية تكون من اليسار أي من الــ
    رقم صفر، هذا العنصر لن نبدأ الترتيب من عنده ، بل سنبدأ من العنصر الذي يليه ، أي من العنصر Index
    الذي يحمل الــ index رقم 1
    نأخذ العدد (1) ونحتفظ بقيمته في متغير مؤقت وليكن
    temp
    ، ونبدأ بالتشيك على الأرقام التي تسبقه رقماً رقماً ، أي على العدد (Cool هنا ، إذا كان العدد (1) أصغر من العدد (8 ) ، سوف نعمل على إقحام (إدخال أو حشر ) العنصر (1) في مكانه الصحيح وذلك بسحب (Cool مكان (1) ونضع (1) في مكانه الصحيح ..
    لكي تصبح المصفوفة بالشكل التالي ..

    4 2 7 8 1

    نأتي للـ
    index
    رقم 2 ، والذي يحمل العدد (7 ) ، ونبدأ بالتشييك على الأرقام قبله بعد الاحتفاظ بقيمة (7) في المتغير المؤقت، نجد أن (8 ) أكبر من (7 ) ، إذاً نسحب (Cool مكان (7) ونكمل البحث إلى الخلف
    ، هل (7 ) أصغر من (1 ) ؟ لا ، إذا نتوقف عند 1 وهو أقل من 7 ،ونقحم (7) مكان (Cool المزاحة، ويصبح شكل المصفوفة الجديد كالتالي

    4 2 8 7 1

    الآن نأتي للــ
    index
    رقم 3 والذي يحمل العدد ( 2 ) ، ونحتفظ بقيمة (2) في المتغير المؤقت ،ونعود بالتشييك إلى الخلف ،
    هل 2 أصغر من 8 ؟
    نعم ، إذا نسحب (Cool مكان (2)
    ولكن لم ننتهي هنا من التشييك ، نكمل
    هل 2 أصغر من 7 ؟
    نعم ، إذا نسحب (7) أيضاً ، ونكمل..


    هل 2 أصغر من 1 ؟
    لا ، إذا لا نعمل سحب للـ (1)
    وبما أننا وصلنا لعدد أصغر من 2 ، إذاً نتوقف عن التشييك، ونقحم (2) في مكانه الصحيح..

    إذا شكل المصفوفة النهائي بعد هذه الدورة
    4 8 7 2 1

    نأخذ الآن الــ
    Index
    رقم 4 ، والذي يحمل العدد 4 ، نحتفظ بالعدد (4) في متغير مؤقت ،ونعود أيضاً بالتشييك إلى الخلف
    هل 4 أصغر من 8 ؟ نعم ، إذا نسحب (Cool مكان (4)
    ونكمل التشييك إلى الخانة
    Index
    رقم صفر، أو إلى أن نصل إلى عدد أصغر من 4 ، أي أن جميع الأرقام قبل 4 من هذا العدد مرتبة
    هل 4 أصغر من 7 ؟ نعم إذا نسحب(7) أيضاً..

    هل 4 أصغر من 2 ؟ لا ، إذاً نتوقف عن التشييك، بحكم أن جميع الأرقام قبل 2 مرتبة ومن المؤكد أيضاً أنها أصغر من 4 ، إذا نقحم العدد (4) ، وسيكون الشكل النهائي للمصفوفة إلى الآن كالتالي
    8 7 4 2 1

    وبما أننا وصلنا إلى الخانة رقم 4 ، فهذا يعني أننا وصلنا إلى نهاية المصفوفة، فالخانة الأخيرة للمصفوفة هي 4 وحجمها هو 5 ..

    لاحظ الآن أن المصفوفة الـ
    array
    أصبحت مرتبة ترتيباً تصاعدياً
    Ascending order
    أي من الأصغر إلى الأكبر، وهذه هي فكرة هذه الخوارزمية، وهي إقحام أوإدخال أو حشر العنصر في مكانه الصحيح، ففي كل دوره
    Loop
    نقوم بإدخال عنصر واحد في مكانه الصحيح ...


    ================================================== =======

    معلومات إضافية:
    تعقيد الوقت لهذه الخوارزمية
    Time complexity
    في أفضل الحالات أي عندما تكون مرتبة =
    O(n)
    وفي أسوأ الحالات أي عندما لا تكون مرتبة=
    O(n^2)


    ===============================

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

      الوقت/التاريخ الآن هو الخميس أغسطس 24, 2017 4:41 am