كل ما تريد معرفته عن فرز سريع

الفرز السريع (بالإنجليزية: Quicksort) هي خوارزمية لفرز المصفوفات (تصاعديّا أو تنازليّا) من ابتكار الإنجليزي توني هور في 1961.

فرز سريع هي خوارزمية فرز فعالة. تم تطويره بواسطة عالم الكمبيوتر البريطاني توني هور في عام 1959 ونشر في عام 1961، ولا يزال خوارزمية الفرز شائعة الاستخدام. عندما يتم تنفيذه بشكل جيد، يمكن أن يكون أسرع إلى حد ما من دمج الفرز وحوالي مرتين أو ثلاث مرات أسرع من فرز الكومة.

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

كما أن الترتيبال سريع هو نوع للمقارنة، مما يعني أنه يمكنه فرز العناصر من أي نوع يتم تحديد علاقة «أقل من» (رسميًا، فرز إجمالي). لا تعد عمليات التنفيذ الفعالة لـ فرز سريع من النوع المستقر، مما يعني أنه لا يتم الاحتفاظ بالفرز النسبي لعناصر الفرز المتساوية.

يُظهر التحليل الرياضي للفرز السريع أن الخوارزمية، في المتوسط، تأخذ O (n سجل ن) مقارنات لفرز ن العناصر. في أسوأ الحالات، تقوم بإجراء مقارنات O (n 2)، على الرغم من أن هذا السلوك نادر.