19. فرز الإدراج (Insertion Sort): المفهوم والتطبيق (O(N²))

غالباً ما تتم مقارنة فرز الإدراج بفرز يد من أوراق اللعب. وهو فعال للغاية للمصفوفات الصغيرة أو المصفوفات المفرزة تقريباً.

المفهوم

يتكرر عبر المصفوفة، ويأخذ عنصراً واحداً في كل مرة (المفتاح 'key') ويدرجه في موضعه الصحيح داخل الجزء المفرز بالفعل من المصفوفة.

خطوات التطبيق

1. البدء بالعنصر الثاني (بافتراض أن الأول مفرز).
2. أخذ هذا العنصر (المفتاح key).
3. إزاحة العناصر في الجزء المفرز التي هي أكبر من المفتاح بموضع واحد إلى اليمين.
4. إدراج المفتاح في المكان المفتوح.

python def insertion_sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 # Move elements of arr[0..i-1], that are greater than key, # to one position ahead of their current position while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr