الترتيب السريع

الترتيب السريع (quick sort) خوارزمية ترتيب فعّالة واسعة الانتشار تقوم على استراتيجية التقسيم والتغلب.

العملية الجوهرية في الترتيب السريع هي «التقسيم بالمحمّي» (sentinel partitioning)، وهدفها اختيار عنصر «محوراً»، ونقل جميع العناصر الأصغر من المحور إلى يساره، وجميع العناصر الأكبر منه إلى يمينه. ويوضح الشكل أدناه هذه العملية تحديداً.

1. اختر العنصر الواقع في أقصى اليسار محوراً، ونهيّئ مؤشرين i وj عند طرفي المصفوفة.
2. ادخل في حلقة. في كل جولة، استخدم i (j) لإيجاد أول عنصر أكبر (أصغر) من المحور، ثم بدّل العنصرين.
3. كرّر الخطوة 2. حتى يلتقي i وj، ثم بدّل المحور إلى الموضع الحدّي بين المصفوفتين الفرعيتين.

بعد التقسيم بالمحمّي، تُقسَّم المصفوفة الأصلية إلى ثلاثة أجزاء: المصفوفة الفرعية اليسرى، والمحور، والمصفوفة الفرعية اليمنى، بحيث «أي عنصر في المصفوفة الفرعية اليسرى $\leq$ المحور $\leq$ أي عنصر في المصفوفة الفرعية اليمنى». لذلك لا يلزمنا تالياً سوى ترتيب المصفوفتين الفرعيتين.

/* التقسيم بالمحمّي */
func (q *quickSort) partition(nums []int, left, right int) int {
	// استخدم nums[left] محوراً
	i, j := left, right
	for i < j {
		for i < j && nums[j] >= nums[left] {
			j-- // ابحث من اليمين إلى اليسار عن أول عنصر أصغر من المحور
		}
		for i < j && nums[i] <= nums[left] {
			i++ // ابحث من اليسار إلى اليمين عن أول عنصر أكبر من المحور
		}
		// بدّل العنصرين
		nums[i], nums[j] = nums[j], nums[i]
	}
	// بدّل المحور إلى الحد الفاصل بين المصفوفتين الفرعيتين
	nums[i], nums[left] = nums[left], nums[i]
	return i // أعد فهرس المحور
}

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

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

1. أولاً، نفّذ «تقسيمًا بالمحمّي» واحداً على المصفوفة الأصلية للحصول على المصفوفتين الفرعيتين اليسرى واليمنى غير المرتبتين.
2. ثم نفّذ «التقسيم بالمحمّي» تعاودياً على المصفوفة الفرعية اليسرى والمصفوفة الفرعية اليمنى على التوالي.
3. واصل التعاود حتى يصبح طول المصفوفة الفرعية 1، وعندها يكتمل ترتيب المصفوفة بأكملها.

/* الترتيب السريع */
func (q *quickSort) quickSort(nums []int, left, right int) {
	// أوقف التعاود عندما يصبح طول المصفوفة الفرعية 1
	if left >= right {
		return
	}
	// التقسيم بالمحمّي
	pivot := q.partition(nums, left, right)
	// عالج المصفوفتين الفرعيتين اليسرى واليمنى تعاودياً
	q.quickSort(nums, left, pivot-1)
	q.quickSort(nums, pivot+1, right)
}

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

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

لماذا يُعدّ الترتيب السريع سريعاً

كما يوحي اسمه، للترتيب السريع ميزة كفاءة واضحة. وعلى الرغم من أن تعقيده الزمني المتوسط مماثل لتعقيد «ترتيب الدمج» و«ترتيب الكومة»، فإن الترتيب السريع أسرع عادةً في الممارسة العملية للأسباب التالية.

• أسوأ حالة غير مرجّحة الحدوث: على الرغم من أن التعقيد الزمني للترتيب السريع في أسوأ حالة هو $O(n^2)$ وأن أداءه أقل قابلية للتنبؤ من أداء ترتيب الدمج، فإن الترتيب السريع يعمل في زمن $O(n \log n)$ في الغالبية العظمى من الحالات.
• كفاءة عالية في ذاكرة التخزين المؤقت: أثناء التقسيم بالمحمّي، يستطيع النظام تحميل المصفوفة الفرعية بأكملها في ذاكرة التخزين المؤقت، فيكون الوصول إلى العناصر فعّالاً نسبياً. في المقابل، تتطلب خوارزميات مثل «ترتيب الكومة» وصولاً غير متجاور إلى العناصر، فلا تنال هذه الميزة.
• عوامل ثابتة صغيرة: من بين الخوارزميات الثلاث أعلاه، يُجري الترتيب السريع أقل عدد إجمالي من المقارنات والإسنادات والتبديلات. وهذا مشابه لسبب كون «ترتيب الإدراج» أسرع من «ترتيب الفقاعات».

تحسين المحور

قد ينخفض زمن الترتيب السريع في بعض المدخلات. تأمّل مثالاً متطرفاً تكون فيه مصفوفة الإدخال مرتبة تنازلياً بالكامل. ولأننا نختار العنصر الواقع في أقصى اليسار محوراً، فبمجرد اكتمال التقسيم بالمحمّي يُبدَّل المحور إلى أقصى يمين المصفوفة، فتبقى مصفوفة فرعية يسرى طولها $n - 1$ ومصفوفة فرعية يمنى طولها $0$. وإذا استمر ذلك تعاودياً، ينتج عن كل جولة من التقسيم بالمحمّي مصفوفة فرعية واحدة طولها $0$، فتنهار استراتيجية التقسيم والتغلب، وينحدر الترتيب السريع إلى ما يقارب «ترتيب الفقاعات».

لتقليل احتمال حدوث ذلك، يمكننا تحسين استراتيجية اختيار المحور المستخدمة في التقسيم بالمحمّي. فمثلاً يمكننا اختيار محور عشوائياً. غير أنه إذا حالفنا سوء الحظ واخترنا محاور سيئة مراراً، فقد يظل الأداء غير مُرضٍ.

تجدر الإشارة إلى أن لغات البرمجة تولّد عادةً «أعداداً شبه عشوائية». وإذا أنشأنا حالة اختبار محددة تستهدف متتالية شبه عشوائية، فقد يظل الترتيب السريع يعاني أداءً متدهوراً.

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

وتكون شيفرة المثال كما يلي:

/* التقسيم بالمحمّي */
func (q *quickSort) partition(nums []int, left, right int) int {
	// استخدم nums[left] محوراً
	i, j := left, right
	for i < j {
		for i < j && nums[j] >= nums[left] {
			j-- // ابحث من اليمين إلى اليسار عن أول عنصر أصغر من المحور
		}
		for i < j && nums[i] <= nums[left] {
			i++ // ابحث من اليسار إلى اليمين عن أول عنصر أكبر من المحور
		}
		// بدّل العنصرين
		nums[i], nums[j] = nums[j], nums[i]
	}
	// بدّل المحور إلى الحد الفاصل بين المصفوفتين الفرعيتين
	nums[i], nums[left] = nums[left], nums[i]
	return i // أعد فهرس المحور
}

تحسين عمق التعاود

قد يستهلك الترتيب السريع أيضاً مساحة أكبر في بعض المدخلات. تأمّل مصفوفة إدخال مرتبة بالكامل. وليكن طول المصفوفة الفرعية الحالية في التعاود $m$. ينتج عن كل جولة من التقسيم بالمحمّي مصفوفة فرعية يسرى طولها $0$ ومصفوفة فرعية يمنى طولها $m - 1$، مما يعني أن كل استدعاء تعاودي يقلّص حجم المسألة بمقدار عنصر واحد فقط. وبذلك يمكن أن تبلغ شجرة التعاود ارتفاعاً قدره $n - 1$، مستهلكة مساحة إطار مكدس $O(n)$.

لمنع تراكم إطارات المكدس، يمكننا مقارنة طولي المصفوفتين الفرعيتين بعد كل جولة من التقسيم بالمحمّي، والتعاود على المصفوفة الأقصر فقط. ولأن طول المصفوفة الفرعية الأقصر لا يتجاوز $n / 2$، يضمن هذا الأسلوب ألا يتجاوز عمق التعاود $\log n$، مما يقلل التعقيد المكاني في أسوأ حالة إلى $O(\log n)$. وتظهر الشيفرة أدناه:

/* الترتيب السريع */
func (q *quickSort) quickSort(nums []int, left, right int) {
	// أوقف التعاود عندما يصبح طول المصفوفة الفرعية 1
	if left >= right {
		return
	}
	// التقسيم بالمحمّي
	pivot := q.partition(nums, left, right)
	// عالج المصفوفتين الفرعيتين اليسرى واليمنى تعاودياً
	q.quickSort(nums, left, pivot-1)
	q.quickSort(nums, pivot+1, right)
}