Implementation (Part 2)
الدرس 6 من 9 في دورة الترتيب بالإدراج - سلسلة DSA على Coddy.
السيناريو: فرز [5, 2, 9, 1, 5]
الخطوة 1: الحالة الأولية
- المصفوفة الأصلية: [5, 2, 9, 1, 5]
- تخيل هذا كمجموعة أوراق اللعب في يدنا (أو مصفوفة من الأرقام).
الخطوة 2: العنصر الأول (i=1, key=2)
- نبدأ بالبطاقة (العنصر) الثانية: key = 2.
- قارن 2 مع 5 (العنصر الوحيد الذي تم فرزه حتى الآن).
- بما أن 2 أصغر، نقوم بإزاحة 5 إلى اليمين وإدراج 2 في مكانها.
- المصفوفة المحدثة: [2, 5, 9, 1, 5]
الخطوة 3: العنصر الثاني (i=2, key=9)
- انتقل إلى البطاقة التالية: key = 9.
- قارن 9 مع 5.
- بما أن 9 أكبر، فلا داعي للإزاحة.
- المصفوفة المحدثة: [2, 5, 9, 1, 5] (لا يوجد تغيير)
الخطوة 4: العنصر الثالث (i=3, key=1)
- انتقل إلى البطاقة التالية: key = 1.
- قارن 1 مع 9، ثم مع 5.
- أزح 9 و 5 إلى اليمين، لتوفير مساحة لـ 1.
- المصفوفة المحدثة: [1, 2, 5, 9, 5]
الخطوة 5: العنصر الرابع (i=4, key=5)
- انتقل إلى البطاقة التالية: key = 5.
- قارن 5 مع 9.
- بما أن 5 أصغر، فلا داعي للإزاحة.
- المصفوفة المحدثة: [1, 2, 5, 9, 5] (لا يوجد تغيير)
الخطوة 6: العنصر الخامس (i=5, key=5)
- انتقل إلى البطاقة الأخيرة: key = 5.
- قارن 5 مع 9.
- بما أن 5 أصغر، فلا داعي للإزاحة.
- المصفوفة المحدثة: [1, 2, 5, 5, 9]
النتيجة النهائية:
- المصفوفة المفروزة: [1, 2, 5, 5, 9]
في كل خطوة، نختار بطاقة (عنصر)، ونقارنها بالعناصر المفروزة، ونضعها في المكان الصحيح، مع إزاحة العناصر الأخرى إذا لزم الأمر. نكرر هذه العملية حتى يتم فرز المصفوفة بالكامل.
التحدي
سهلالآن، قم بتنفيذ الحلقة الداخلية (inner loop)، التي تقوم بعملية الفرز لكل عنصر.
أكمل عملية الفرز داخل الدالة insertionSort.
يجب أن تقوم الدالة أيضاً بطباعة عناصر المصفوفة في النهاية، واحداً تلو الآخر، مع وجود سطر جديد بين كل عنصر وآخر.
استخدم الدروس السابقة والتلميح كمرجع لك :)
جرّب بنفسك
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
print(key)
جميع دروس الترتيب بالإدراج - سلسلة DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity