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

<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
، ونبدأ بالتشيك على الأرقام التي تسبقه رقماً رقماً ، أي على العدد ( هنا ، إذا كان العدد (1) أصغر من العدد (8 ) ، سوف نعمل على إقحام (إدخال أو حشر ) العنصر (1) في مكانه الصحيح وذلك بسحب ( مكان (1) ونضع (1) في مكانه الصحيح ..
لكي تصبح المصفوفة بالشكل التالي ..

4 2 7 8 1

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

4 2 8 7 1

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


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

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

نأخذ الآن الــ
Index
رقم 4 ، والذي يحمل العدد 4 ، نحتفظ بالعدد (4) في متغير مؤقت ،ونعود أيضاً بالتشييك إلى الخلف
هل 4 أصغر من 8 ؟ نعم ، إذا نسحب ( مكان (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)

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

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