اقرأ في هذا المقال
- ما هي خوارزمية الترتيب بالأدراج Insertion Sort؟
- كيف تعمل خوارزمية الترتيب بالإدراج؟
- خطوات خوارزمية الترتيب بالأدراج
- تطبيقات خوارزمية الترتيب بالإدراج
ما هي خوارزمية الترتيب بالأدراج Insertion Sort؟
وهي خوارزمية تعتمد على المقارنة الموضعية، حيث يتم الاحتفاظ بقائمة فرعية ليتم فرزها دائمًا، على سبيل المثال، يتم الاحتفاظ بالجزء السفلي من المصفوفة ليتم فرزها، ويجب أن يجد العنصر الذي سيتم “إدراجه” في هذه القائمة الفرعية المرتبة مكانه المناسب، ومن ثم يجب إدراجه هناك، ومن هنا جاء الاسم (الترتيب بالإدراج).
تقوم الخوارزمية بالبحث في المصفوفة بشكل تسلسلي، ويتم نقل العناصر التي لم يتم فرزه وإدراجه في القائمة الفرعية التي تم فرزها (في نفس المصفوفة)، هذه الخوارزمية غير مناسبة لمجموعات البيانات الكبيرة حيث أن متوسط درجة تعقيدها وأسوأ حالة لها هي “O(n²)”، حيث “n” هو عدد العناصر.
كيف تعمل خوارزمية الترتيب بالإدراج؟
لتتعرف على كيفية عمل هذه الخوارزمية، دعنا نأخذ مصفوفة غير مرتبة، على سبيل المثال:
تقوم الخوارزمية، بمقارنة أول عنصرين:
تجد أن كلا من (14) و (33) هم بالترتيب تصاعدي بالفعل، في الوقت الحالي، يوجد (14) في القائمة الفرعية التي تم ترتيبها، الآن تتحرك الخوارزمية للأمام وتقارن (33) و (27):
وتجد أن الرقم (33) ليس في الموضع الصحيح (لأن 33 أكبر من 27)، فتقوم باستبدال (33) بـ (27)، وتتحقق أيضًا من جميع عناصر القائمة الفرعية التي تم فرزها، هنا نرى أن القائمة الفرعية التي تم فرزها تحتوي على عنصر واحد فقط (14)، و (27) أكبر من (14)، بالتالي، فإن القائمة الفرعية التي تم فرزها تظل مرتبة بعد التبديل:
الآن لدينا (14) و (27) في القائمة الفرعية المرتبة، بعد ذلك، تتم مقارنة (33) مع (10):
(33) هي أكبر من (10)، أي انهم ليسوا بالترتيب التصاعدي:
لذا، نقوم بتبديلهم:
مع ذلك، فإن تبديلهم تجعل (27) و (10) غير مرتبين، لذا فأننا نقوم بتبديلهم أيضًا:
مرة أخرى، نجد (14) و (10) غير مرتبين، لذا فأننا نقوم بتبديلهم:
تستمر هذه العملية، حتى تتم تغطية جميع القيم غير المرتبة في قائمة فرعية مرتبة.
خطوات خوارزمية الترتيب بالأدراج:
الآن وقد اصبح لدينا صورة أكبر عن كيفية عمل تقنية الترتيب بالأدراج، يمكنك استنباط خطوات بسيطة يمكننا من خلالها تحقيق فرز الإدراج:
الخطوة 1: كرر من “[1]arr” إلى “[n]arr”، أي حتى تكمل كل المصفوفة
الخطوة 2: قارن العنصر الحالي (المفتاح) بالعنصر التالي.
الخطوة 3: إذا كان العنصر الحالي أكبر من العنصر التالي، فقم بتبديلهم.
الخطوة 4: قارن مع جميع العناصر في القائمة الفرعية المرتبة (إذا كان العنصر الحالي أصغر من العنصر السابق، فقارنه بالعناصر السابقة، ثم حرك العناصر الأكبر في موضع واحد لليمين؛ لتوفير مساحة للعنصر الذي تم تبديله).
الخطوة 5: أدخل القيمة.
الخطوة 6: كرر هذه العملية حتى يتم فرز القائمة.
تطبيقات خوارزمية الترتيب بالإدراج:
يتم استخدام فرز الإدخال إذا:
- كانت المصفوفة فيها عدد قليل من العناصر.
- لم يتبق سوى عدد قليل من العناصر ليتم ترتيبها.
