ترتيب سريع
الترتيب السريع quicksort هوكيفية ترتيب من اختراع هوار (C.A.R.Hoare) في 1962.
تفضيلات وخوارزمية
تنبني الخوارزمية على وضع العنصر الأول (يسمى مؤشر) في مكانه النهائي ثم وضع العناصر الأكبر من المؤشر من جهة اليمين والعناصر الأصغر من جهة اليسار. وتسمى هذه العملية تجزئة. وبالنسبة لكل تحت-جدول، نحدد مؤشرا جديدا ونعيد عملية التجزئة. تتكرر هذه العملية إلى حتى نحصل على مجموعة مرتبة.
إذا تم اختيار المؤشر بطريقة سليمة، نحصل على الطريقة الأسرع للترتيب في الحالة المتوسطة، مع تعقيد ب. والتي قد تتحول إلى في الحالة الأصعب، وهي حالة جدول عناصره مرتبة أصلا. ولكن هذه الحالة بديهية لأن المجموعة مرتبة أصلا.
في الناحية العملية، بالنسبة للتجزئات مع عدد قليل لا يتجاوز بضع عشرات من العناصر، يتم اللجوء عادة إلى الترتيب بالإدراج الذيقد يكون أفضل من الترتيب السريع.
وبصفة عامة يعتبر الترتيب السريع الأكثر شيوعا (شعبية) من بين جميع خوارزميات الترتيب.
المشكلة الوحيدة تتمثل في كيفية اختيار المؤشر.
اختيار أفضل مؤشر
عند استعمال الترتيب السريع لمجموعة مرتبة مسبقا، وبطريقة اعتباطية، يستغرق كما قلنا وقتا كبيرا، وذلك راجع لأن أول عنصر هوالذي يعتبر مؤشرا، الشيء الذي يؤدي إلى عدم تقسيم المجموعة إلى قسمين أكبر وأصغر من المؤشر. لحل المشكل يتم اختيار العنصر الأوسط، كما يمكن اختياره عشوائيا من عنصرين متواجدين حول المركز, حيث حتى عملية اختيار المؤشر أو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);
| |
|
بالفقاعات · بالإختيار · بالإدراج · سريع · |
