خوارزمية الفرز بالإدخال (Insertion Sort)

إنّ الغاية من خوارزميات الفرز (الترتيب) هي ترتيب أو فهرسة العناصر تصاعديًا أو تنازليًا، يمكن أن تكون هذه العناصر مجموعات من الأعداد، أو المحارف، أو أي بنية تحوي أحد هذه الأنماط.

تحدّثنا في مقالات سابقة عن خوارزميتي الفرز الفقاعي (Bubble Sort) والفرز بالاختيار (Selection Sort)، الآن سنكمل في سلسلتنا ونبدأ بالحديث عن خوارزمية الفرز بالإدخال (Insertion Sort).

ماهي خوارزمية الفرز بالإدخال؟

خوارزمية الفرز بالإدخال هي خوارزمية مبنية على فكرة  أخذ عنصر واحد من عناصر الدخل ضمن كل دور (Iteration) وإيجاد موقعه الصحيح في المصفوفة النهائية (المرتبة)، التي يتمّ بناءها من خلال إضافة العناصر، واحدًا تلو الآخر، مع كل دور.

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

ماهي آلية عمل الخوارزمية؟

فلنفترض أنّ لدينا مصفوفة A غير مرتبة تحتوي على n عنصر، والمطلوب هو ترتيب العناصر تصاعدياً، فلنفرض أن المصفوفة تحتوي على العناصر الآتية : {7 , 4 , 5 , 2}

أولًا؛ إدخال الرقم 7، طالما أنّه أول عنصر يُدخَل إلى المصفوفة، بالتالي لا يوجد عناصر ليُقارَن معها، ويبقى في موقع الافتراضي (الخانة الأولى).

ثانيًا؛ إدخال الرقم 4، الرقم 7 هو أكبر عنصر في المصفوفة المرتبة الحالية، ثمّ إنّ  7>4، يتم تحريك الرقم 4 إلى موقعه الصحيح (الخانة الأولى) قبل الرقم 7 وإزاحة 7 نحو اليمين بمقدار 1.

ثالثًا؛ إدخال الرقم5، مشابه لما حصل في ثانيًا؛ يُقارن مع أكبر عنصر في المصفوفة المرتبة الحالية وهو الرقم 7، ثمّ إنّ 7>5، وبالتالي يتم تحريك الرقم 5 إلى موقعه الصحيح.

رابعًا؛ إدخال الرقم 2، نلاحظ أنّه أصغر من كل العناصر الموجود على يساره، وبالتالي يتم نقله إلى الخانة الأولى، وإزاحة كل العناصر نحو اليمين بمقدار 1.

لتنتج في النهاية المصفوفة المرتبة [2 , 4 , 5 , 7].

مثال برمجي لتوضيح آلية العمل:

درجة تعقيد الخوارزمية (Time Complexity)

تعقيد تربيعي

O(n2)

السبب: في الحالة الأسوأ، يتمّ مقارنة كل عنصر مع كل العناصر الأُخرى في المصفوفة المُرتّبة. ومن أجل N عنصر، لدينا N2 عملية مقارنة.
وبالتالي تكون النتيجة من رتبة:

O(n2)

مشروعنا غير ربحي، ومُموّل ذاتيًا، نحن لا نتلقى أي أموال حكومية أو من أي جهة كانت سياسية أو غيرها، كما أنّنا لا نلتمس ذلك. و بالإضافة للتمويل الذاتي، الذي يبلغ حاليا 99٪ من مجمل التمويل، نحن نعتمد على المساهمة الطوعية لمؤسسات خاصة وأفراد مثلك لتطوير المشروع وتحقيق أهدافه. لدعمنا إضغط هنا

  • إعداد: نور عبدو
تعليقات
Loading...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More