ترتيب سريع

☰ جدول المحتويات

نبذة تمهيدية
تفضيلات وخوارزمية
- اختيار أفضل مؤشر
- تحسينات أخرى
خطوات الخوارزمية
- مثال
مراجع

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

الترتيب السريع (Quicksort) هي خوارزمية لترتيب المصفوفات (تصاعديّا أو تنازليّا) من ابتكار الإنجليزي توني هور في 1961.^[1]^[2]^[3]^[4]

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

تنبني الخوارزمية على وضع العنصر الأول في المصفوفة (بإتخاذه محورًا), ثم ترتيب ووضع العناصر الأكبر من هذا المحور إلى جهة اليمنى من المصفوفة ووضع العناصر الأصغر في الجهة اليسرى. بهذه الطريقة يعتبر المحور في مكانه النهائي المرتّب. تسمى هذه العملية تجزئة ليتبقى من المصفوفة جزئين لم يتم ترتيبهما. نقوم بعد ذلك بإعادة هذه الطريقة على الجزئين المتبقيين من المصفوفة وهكذا نحدد محورا جديدا ونعيد عملية التجزئة. تتكرر هذه العملية إلى أن نحصل على مجموعة مرتبة.

إذا تم اختيار المحور بطريقة صحيحة، نحصل على الطريقة الأسرع للترتيب في الحالة المتوسطة، مع تعقيد ب $\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 فيصبح لدينا مصموفة

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

مثال

algorithm quicksort(A, lo, hi) is if lo < hi then p := partition(A, lo, hi) quicksort(A, lo, p – 1) quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is pivot := A[hi] i := lo // place for swapping for j := lo to hi – 1 do if A[j] ≤ pivot then swap A[i] with A[j] i := i + 1 swap A[i] with A[hi] return i

يتم ترتيب المصفوفة باستدعاء quicksort(A, 1, length(A)).

مراجع

[1], [2] - تصفح: نسخة محفوظة 23 أكتوبر 2017 على موقع واي باك مشين.
Sedgewick, R. (1978). "Implementing Quicksort programs". Comm. ACM. 21 (10): 847–857. doi:10.1145/359619.359631.
"Sir Antony Hoare". Computer History Museum. مؤرشف من الأصل في 3 أبريل 201522 أبريل 2015.
الترتيب السريع لشارلس أنطوني هاور - تصفح: نسخة محفوظة 22 أبريل 2016 على موقع واي باك مشين.

خوارزميات الترتيب

بالفقاعات · بالاختيار · بالإدراج · سريع · انتقائي · دمجي