Insertion Sort: أسهل Sorting Algorithm للمبتدئين

الـInsertion Sort من أبسط الـSorting Algorithms اللي ممكن تبدأ بيها، وسهل تفهمه وتطبقه
النهاردة هنتكلم عن Insertion Sort، مميزاته، عيوبه، وإزاي يشتغل خطوة بخطوة.

الفكرة العامة: ترتيب الأرقام أو الأوراق ​

تخيل معايا إنك عايز ترتب مجموعة أوراق لعب:

• تمسك كل ورقة وتحطها في مكانها الصحيح بين الباقي.
• المكان الصحيح بيتحدد بالنسبة للـreference اللي غالبًا أول عنصر في الـArray.
• اللي على شمال العنصر أقل منه، واللي على يمينه أكبر منه (لو عايزين ترتيب تصاعدي).
• العنصر يتحرك في اتجاه واحد بس للخلف لحد ما يوصل مكانه الصحيح.

مثال عملي على Array غير مترتبة ​

نفترض عندنا Array فيها 10 أرقام مش مترتبة، وعايزين نرتبها تصاعديًا:

• نعتبر أول رقم موجود في مكانه الصحيح ويكون هو الـReference.
• تاني رقم: لو أكبر من الـReference سيبه في مكانه، لو أقل حطه قبل الـReference.
• تالت رقم: نقارنه باللي قبله ونحطه في مكانه الصحيح بين العناصر.
• نكمل العملية لكل عناصر الـArray.
• لما نخلص، الـArray تبقى مرتبة.

الكود العملي في Python ​

def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# نحرك العناصر الأكبر للخلف
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr

# مثال استخدام

arr = [9, 5, 1, 4, 3]
sorted_arr = insertion_sort(arr)
print(sorted_arr)  # الناتج: [1, 3, 4, 5, 9]

تحليل الأداء: Time Complexity ​

• أسوأ حالة: O(n^2) - لو الـArray مقلوبة أو عشوائية جدًا.
• أفضل حالة: O - لو الـArray مرتبة أصلاً.
• متوسط الحالة: O(n^2).

مميزات Insertion Sort ​

• سهل جدًا في الكتابة والفهم.
• مش محتاج مساحة إضافية في الذاكرة (In-place Sorting).
• مناسب للـArrays الصغيرة أو تقريبًا مرتبة.

عيوب Insertion Sort ​

• بطئ مقارنة بالـSorting Algorithms التانية زي Quick Sort أو Merge Sort.
• مش مناسب للـArrays الكبيرة جدًا بسبب Time Complexity.

نصائح عملية عند استخدام Insertion Sort ​

• استخدمه لما يكون حجم الـArray صغير أو شبه مرتب.
• لو البيانات كبيرة، فكر في Quick Sort أو Merge Sort بدلها.
• مناسب كجزء من Hybrid Sorting Algorithms زي TimSort.