ترتيب الإدراج

ترتيب الإدراج (insertion sort) خوارزمية ترتيب بسيطة، ويعمل عملها على نحو شبيه جداً بعملية ترتيب مجموعة من البطاقات يدوياً.

وتحديداً، نختار عنصراً أساسياً من الجزء غير المرتب، ونقارنه واحداً واحداً بالعناصر في الجزء المرتب الواقع على يساره، ثم ندرجه في موضعه الصحيح.

ويوضح الشكل أدناه كيفية إدراج عنصر في مصفوفة. ولنكن العنصر الأساسي base. نحتاج إلى إزاحة جميع العناصر الواقعة بين الفهرس المستهدف وbase موضعاً واحداً إلى اليمين، ثم إسناد base إلى الفهرس المستهدف.

سير الخوارزمية

يوضح الشكل أدناه السير العام لترتيب الإدراج.

1. في البداية يكون العنصر الأول من المصفوفة مرتباً بالفعل.
2. اختر العنصر الثاني من المصفوفة عنصراً أساسياً base، وبعد إدراجه في موضعه الصحيح يصبح العنصران الأولان من المصفوفة مرتبين.
3. اختر العنصر الثالث عنصراً أساسياً base، وبعد إدراجه في موضعه الصحيح تصبح العناصر الثلاثة الأولى من المصفوفة مرتبة.
4. وهكذا دواليك. في الجولة الأخيرة، اختر العنصر الأخير عنصراً أساسياً base، وبعد إدراجه في موضعه الصحيح تصبح جميع العناصر مرتبة.

وتظهر الشيفرة المثالية أدناه:

/* ترتيب الإدراج */
func insertionSort(nums []int) {
	// الحلقة الخارجية: المجال المرتب هو [0, i-1]
	for i := 1; i < len(nums); i++ {
		base := nums[i]
		j := i - 1
		// الحلقة الداخلية: أدرج base في موضعه الصحيح ضمن المجال المرتب [0, i-1]
		for j >= 0 && nums[j] > base {
			nums[j+1] = nums[j] // أزح nums[j] موضعاً واحداً إلى اليمين
			j--
		}
		nums[j+1] = base // أسند base إلى الموضع الصحيح
	}
}

/* ترتيب الإدراج */
function insertionSort(nums: number[]): void {
    // الحلقة الخارجية: المجال المرتب هو [0, i-1]
    for (let i = 1; i < nums.length; i++) {
        const base = nums[i];
        let j = i - 1;
        // الحلقة الداخلية: أدرج base في موضعه الصحيح ضمن المجال المرتب [0, i-1]
        while (j >= 0 && nums[j] > base) {
            nums[j + 1] = nums[j]; // أزح nums[j] موضعاً واحداً إلى اليمين
            j--;
        }
        nums[j + 1] = base; // أسند base إلى الموضع الصحيح
    }
}

خصائص الخوارزمية

• التعقيد الزمني $O(n^2)$؛ ترتيب تكيّفي (adaptive): في أسوأ حالة تتطلب عمليات الإدراج $n - 1$ و$n-2$ و$\dots$ و$2$ و$1$ تكرار على التوالي، ومجموعها $(n - 1) n / 2$، لذا يكون التعقيد الزمني $O(n^2)$. وعندما تكون البيانات مرتبة بالفعل، تنتهي كل عملية إدراج مبكراً. وعندما تكون مصفوفة الإدخال مرتبة تماماً، يحقق ترتيب الإدراج أفضل تعقيد زمني له $O(n)$.
• التعقيد المكاني $O(1)$؛ ترتيب في المكان (in-place): يستخدم المؤشران $i$ و$j$ مقداراً ثابتاً من المساحة الإضافية.
• ترتيب مستقر: أثناء الإدراج نضع العناصر على يمين العناصر المساوية لها، فيبقى ترتيبها النسبي دون تغيير.

مزايا ترتيب الإدراج

التعقيد الزمني لترتيب الإدراج هو $O(n^2)$، بينما التعقيد الزمني للترتيب السريع (quick sort)، الذي سنتعلّمه لاحقاً، هو $O(n \log n)$. ورغم أن التعقيد الزمني لترتيب الإدراج أعلى، فإنه عادةً أسرع على مجموعات البيانات الصغيرة.

وهذا الاستنتاج شبيه بالاستنتاج المتعلق بالحالات التي يصلح فيها البحث الخطي والبحث الثنائي. فالخوارزميات مثل الترتيب السريع ذي التعقيد $O(n \log n)$ هي خوارزميات ترتيب قائمة على تقسيم وتغلب، وغالباً ما تتضمن عمليات أولية أكثر. وعندما تكون مجموعة البيانات صغيرة، تكون قيمتا $n^2$ و$n \log n$ متقاربتين نسبياً، فلا يهيمن التعقيد المقارب، بل يصبح عدد العمليات الأولية في كل جولة هو العامل الحاسم.

وفي الواقع، تستخدم دوال الترتيب المدمجة في كثير من لغات البرمجة (مثل Java) ترتيب الإدراج. والفكرة العامة هي: للمصفوفات الكبيرة استخدم خوارزميات ترتيب قائمة على تقسيم وتغلب مثل الترتيب السريع؛ وللمصفوفات القصيرة استخدم ترتيب الإدراج مباشرة.

ورغم أن ترتيب الفقاعات وترتيب الاختيار وترتيب الإدراج جميعها بتعقيد زمني $O(n^2)$، فإن ترتيب الإدراج يُستخدم فعلياً أكثر بكثير من ترتيب الفقاعات وترتيب الاختيار، للأسباب التالية أساساً.

• يُنفَّذ ترتيب الفقاعات عبر تبديل العناصر، وهو ما يتطلب متغيراً مؤقتاً ويتضمن $3$ عمليات أولية؛ أما ترتيب الإدراج فيُنفَّذ عبر إسناد العناصر ويتطلب عملية أولية واحدة فقط. لذلك تكون التكلفة الحسابية لترتيب الفقاعات عادةً أعلى من ترتيب الإدراج.
• التعقيد الزمني لترتيب الاختيار هو $O(n^2)$ في جميع الحالات. وإذا أُعطيت مجموعة من البيانات المرتبة جزئياً، كان ترتيب الإدراج عادةً أكفأ من ترتيب الاختيار.
• ترتيب الاختيار غير مستقر ولا يمكن تطبيقه على الترتيب متعدد المستويات.