شرح خوارزمية الفرز بالإدراج
خوارزمية الفرز بالإدراج هي خوارزمية فرز بسيطة تعتمد على المقارنة تبني مصفوفة مرتبة عنصراً تلو الآخر. تعمل عن طريق أخذ كل عنصر من الجزء غير المرتب من المصفوفة وإدراجه في موضعه الصحيح داخل الجزء المرتب.
خوارزمية الفرز بالإدراج سهلة الفهم، سهلة التنفيذ، ومفيدة جداً لتعلم كيفية تفكير خوارزميات الفرز. على الرغم من أنها ليست أسرع خوارزمية فرز لمجموعات البيانات الكبيرة، إلا أنها تعمل بشكل جيد على المصفوفات الصغيرة أو المصفوفات المرتبة تقريباً.
مقدمة
الفرز هو أحد أهم العمليات في علوم الحاسوب. يستخدم المطورون الفرز عندما يحتاجون إلى تنظيم الأرقام، الأسماء، التواريخ، الأسعار، الدرجات، نتائج البحث، سجلات قواعد البيانات، أو أي مجموعة من القيم القابلة للمقارنة.
بعد تعلم خوارزميات الفرز الأساسية مثل فقاعة الفرز وفرز الاختيار، تقدم خوارزمية الفرز بالإدراج فكرة مهمة أخرى للمطورين: بدلاً من تبديل القيم المتجاورة بشكل متكرر أو البحث عن أصغر عنصر، تقوم الخوارزمية بإدراج كل قيمة في مكانها الصحيح، على غرار كيفية ترتيب الأشخاص لبطاقات اللعب في أيديهم.
هذا يجعل خوارزمية الفرز بالإدراج خوارزمية بديهية للغاية. عندما يتم اختيار قيمة جديدة، تتم مقارنتها بالقيم التي تسبقها. إذا كانت القيم السابقة أكبر، يتم إزاحتها إلى اليمين حتى يتم العثور على الموضع الصحيح.
ما هي خوارزمية الفرز بالإدراج؟
خوارزمية الفرز بالإدراج هي خوارزمية فرز تقسم المصفوفة إلى جزأين: جزء مرتب وجزء غير مرتب. في البداية، يعتبر العنصر الأول مرتباً. ثم تأخذ الخوارزمية العنصر التالي وتدرجه في موضعه الصحيح داخل الجزء المرتب.
تستمر العملية حتى يتم إدراج كل عنصر في موضعه الصحيح.
الفكرة الرئيسية بسيطة:
ابدأ من العنصر الثاني.
قارنه بالعناصر التي تسبقه.
أزح العناصر الأكبر موضعاً واحداً إلى اليمين.
أدرج العنصر الحالي في الموضع الصحيح.
كرر حتى تصبح المصفوفة مرتبة.
يطلق على خوارزمية الفرز بالإدراج اسم "إدراج" لأن كل عنصر يتم إدراجه في مكانه الصحيح في الجزء المرتب من المصفوفة.
كيف تعمل خوارزمية الفرز بالإدراج
تعمل خوارزمية الفرز بالإدراج عن طريق توسيع الجزء المرتب من المصفوفة تدريجياً. تفترض الخوارزمية أن العنصر الأول مرتب بالفعل لأن عنصراً واحداً يكون دائماً مرتباً بحد ذاته.
ثم تبدأ بالعنصر الثاني وتخزنه كقيمة حالية. تقارن الخوارزمية هذه القيمة الحالية بالعناصر التي تسبقها. إذا كان عنصر سابق أكبر من القيمة الحالية، يتم إزاحة هذا العنصر السابق إلى اليمين.
عندما يتم العثور على الموضع الصحيح، يتم وضع القيمة الحالية هناك. يستمر هذا حتى تتم معالجة جميع العناصر.
بكلمات بسيطة، تسأل خوارزمية الفرز بالإدراج سؤالاً متكرراً:
أين يجب إدراج هذا العنصر الحالي داخل الجزء المرتب بالفعل؟
مثال تشغيل يدوي
لنرتب يدوياً مصفوفة الأعداد التالية باستخدام خوارزمية الفرز بالإدراج:
[5, 3, 8, 4, 2]في البداية، يعتبر العنصر الأول مرتباً:
Sorted part: [5]
Unsorted part: [3, 8, 4, 2]الممر 1
العنصر الحالي هو 3. نقارنه بالعنصر السابق 5.
بما أن 5 أكبر من 3، نقوم بإزاحة 5 موضعاً واحداً إلى اليمين.
Before insertion:
[5, 3, 8, 4, 2]
Shift 5 to the right:
[5, 5, 8, 4, 2]
Insert 3:
[3, 5, 8, 4, 2]الآن الجزء المرتب هو:
[3, 5]الممر 2
العنصر الحالي هو 8. نقارنه بـ 5.
بما أن 5 ليس أكبر من 8، لا حاجة لإزاحة. العنصر 8 موجود بالفعل في الموضع الصحيح.
Before insertion:
[3, 5, 8, 4, 2]
After insertion:
[3, 5, 8, 4, 2]الآن الجزء المرتب هو:
[3, 5, 8]الممر 3
العنصر الحالي هو 4. نقارنه بالعناصر السابقة في الجزء المرتب.
أولاً، 8 أكبر من 4، لذلك يتم إزاحة 8 إلى اليمين. ثم 5 أكبر من 4، لذلك يتم إزاحة 5 إلى اليمين. القيمة 3 ليست أكبر من 4، لذلك ندرج 4 بعد 3.
Before insertion:
[3, 5, 8, 4, 2]
Shift 8:
[3, 5, 8, 8, 2]
Shift 5:
[3, 5, 5, 8, 2]
Insert 4:
[3, 4, 5, 8, 2]الآن الجزء المرتب هو:
[3, 4, 5, 8]الممر 4
العنصر الحالي هو 2. نقارنه بجميع العناصر السابقة في الجزء المرتب.
بما أن 8، 5، 4، و 3 كلها أكبر من 2، يتم إزاحة كل منها إلى اليمين. ثم يتم إدراج 2 في البداية.
Before insertion:
[3, 4, 5, 8, 2]
Shift 8:
[3, 4, 5, 8, 8]
Shift 5:
[3, 4, 5, 5, 8]
Shift 4:
[3, 4, 4, 5, 8]
Shift 3:
[3, 3, 4, 5, 8]
Insert 2:
[2, 3, 4, 5, 8]المصفوفة الآن مرتبة.
المصفوفة المرتبة النهائية
[2, 3, 4, 5, 8]يُظهر هذا التشغيل اليدوي السلوك الأساسي لخوارزمية الفرز بالإدراج. الخوارزمية لا تبحث عن أصغر عنصر مثل فرز الاختيار. بدلاً من ذلك، تأخذ عنصراً واحداً في كل مرة وتدرجه في الموضع الصحيح بين العناصر السابقة.
خطوات خوارزمية الفرز بالإدراج
يمكن وصف الخوارزمية باستخدام هذه الخطوات:
