ترتيب سريع

الترتيب السريع quicksort هو طريقة ترتيب من اختراع هوار (C.A.R.Hoare) في 1962.

ترتيب سريع لمجموعة اعداد, الخط الافقي هو المؤشر

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

 تفضيلات و خوارزمية

تنبني الخوارزمية على وضع العنصر الأول (يسمى مؤشر) في مكانه النهائي ثم وضع العناصر الأكبر من المؤشر من جهة اليمين و العناصر الأصغر من جهة اليسار. و تسمى هذه العملية تجزئة. و بالنسبة لكل تحت-جدول، نحدد مؤشرا جديدا و نعيد عملية التجزئة. تتكرر هذه العملية إلى أن نحصل على مجموعة مرتبة.

إذا تم اختيار المؤشر بطريقة صحيحة، نحصل على الطريقة الأسرع للترتيب في الحالة المتوسطة، مع تعقيد ب$\Theta (n\log n)$. و التي قد تتحول إلى $\Theta (n^{2})$ في الحالة الأصعب، و هي حالة جدول عناصره مرتبة أصلا. و لكن هذه الحالة بديهية لأن المجموعة مرتبة أصلا.

في الناحية العملية، بالنسبة للتجزئات مع عدد قليل لا يتجاوز بضع عشرات من العناصر، يتم اللجوء عادة إلى الترتيب بالإدراج الذي يكون أفضل من الترتيب السريع.

و بصفة عامة يعتبر الترتيب السريع الأكثر شيوعا (شعبية) من بين جميع خوارزميات الترتيب.

المشكلة الوحيدة تتمثل في كيفية اختيار المؤشر.

 اختيار أفضل مؤشر

عند استعمال الترتيب السريع لمجموعة مرتبة مسبقا، و بطريقة اعتباطية، يستغرق كما قلنا وقتا كبيرا، و ذلك راجع لأن أول عنصر هو الذي يعتبر مؤشرا، الشيء الذي يؤدي إلى عدم تقسيم المجموعة إلى قسمين أكبر و أصغر من المؤشر. لحل المشكل يتم اختيار العنصر الأوسط، كما يمكن اختياره عشوائيا من عنصرين متواجدين حول المركز, حيث أن عملية اختيار المؤشر أو Pivot تحدد أداء الخوارزمية و تأرجحها بين و قت التشغيل N*Log n و N^^{2 بصيغة Big O Notation.}

 تحسينات أخرى

عند استعمال الترتيب السريع لترتيب مجموعة ذات عناصر كبيرة، يمكن تغيير تقنية الترتيب عند الوصول إلى مجموعة جزئية غير مرتبة عدد عناصرها صغير،10 أو أقل. الترتيب بالاختيار مناسب في هذه الحالة.

 خطوات الخوارزمية

• أولا : نقوم باختيار المحور أو pivot
• ثانيا : نقوم بإنشاء ثلاث مصفوفات واحد G تحتوي على العناصر التي هي أكبر من المحور , الثانية E و هي تحتوي على عناصر التي هي مساوية

للمحور , الثالثة وهي L وهي تحتوي على العناصر التي هي اقل من المحور

• ثالثا : نقوم بعمل استدعاء ذاتي على المصفوفة L , G
• رابعا : عند الوصول إلى مرحلة تكون فيها عدد العناصر في المصوفة اقل من 2 أي واحد تكون عناصر مصفوفة مرتبة لانها تحتوي على عنصر

واحد فقط !

• خامسا: نقوم بخطوة التجميع وهي تتصمن جمع المصوفات الثلاث في مصفوفة جديدة بترتيب حيث نضع المصفوفة L ثم E ثم G فيصبح لدينا مصموفة

تحتوي على العناصر مرتبة

 مثال

typedef int tab_entiers[MAX];

int rapideEtape(tab_entiers t، int min، int max) {
	int temp = t[max];
	while(max > min) {
		while(max > min && t[min] <= temp) min++;
		if(max > min) {
			t[max] = t[min];
			max--;
			while(max > min && t[max] >= temp) max--;
			if(max > min) {
				t[min] = t[max];
				min++;
			}
		}
	}
	t[max] = temp;
	return max;
}

void rapide(tab_entiers t، int deb، int fin) {
	int mil;
	if(deb < fin) {
		mil = rapideEtape(t،deb،fin);
		if(mil - deb > fin - mil) {
			rapide(t،mil+1،fin);
			rapide(t،deb،mil-1);
		}
		else {
			rapide(t،deb،mil-1);
			rapide(t،mil+1،fin);
		}
	}
}