في الفصل الخامس، رأيت طريقة فرز بسيطة تسمى
فرز الفقاعة. وذكر في ذلك الوقت أن هناك
تقييمات أفضل بكثير. هنا، ستقوم بتطوير إصدار من أفضل الإصدارات: الفرز السريع (الفرز السريع).
التصنيف السريع، اخترعه وأطلق عليه اسم C.A.R. Hoare، هي أفضل خوارزمية تصنيف للأغراض العامة متاحة حاليًا. لم أتمكن من عرضه في الفصل الخامس لأن أفضل تطبيق للفرز السريع يعتمد على التكرار. يقوم الإصدار الذي سنقوم بتطويره بفرز مجموعة من الأحرف، ولكن يمكن تكييف المنطق لفرز أي نوع من الكائنات.
يعتمد الفرز السريع على فكرة الأقسام. يتضمن الإجراء العام تحديد قيمة، تسمى المقارنة، ثم تقسيم المصفوفة إلى قسمين. يتم إدراج جميع العناصر الأكبر من أو تساوي قيمة القسم على جانب واحد ويتم إدراج العناصر الأصغر على الجانب الآخر. يتم تكرار هذه العملية لكل قسم متبقي حتى يتم فرز المصفوفة. على سبيل المثال، بالنظر إلى المصفوفة fedacb واستخدام القيمة d كمقارنة، فإن التمرير الأول للفرز السريع سيعيد ترتيب المصفوفة كما هو موضح أدناه:

الأولي f e d a c b
المقطع 1 ب ج أ د هـ و

ثم يتم تكرار هذه العملية لكل قسم - أي bca وdef. كما ترون، فإن العملية متكررة بطبيعتها، وفي الواقع، فإن التنفيذ الأنظف للفرز السريع هو تكراري.
يمكنك تحديد قيمة المقارنة بطريقتين. يمكنك تحديده بشكل عشوائي أو عن طريق إيجاد متوسط ​​مجموعة صغيرة من القيم المأخوذة من المصفوفة. للحصول على التصنيف الأمثل، يجب عليك تحديد قيمة تقع بالضبط في منتصف نطاق القيمة. ومع ذلك، ليس من السهل القيام بذلك بالنسبة لمعظم مجموعات البيانات. أسوأ الحالات هي عندما تكون القيمة المحددة في أحد الأطراف. ومع ذلك، سيتم تشغيل الفرز السريع بشكل صحيح.
يقوم إصدار الفرز السريع الذي سنقوم بتطويره بتحديد العنصر الأوسط من المصفوفة كعنصر مقارنة.

راجع QSDemo.java.

فرز سريع:

• واحدة من خوارزميات التصنيف الأكثر كفاءة والأكثر استخدامًا.
• اخترعها C.A.R. هور.
• استنادًا إلى مفهوم الأقسام، حيث يتم تقسيم المصفوفة إلى أقسام يتم فرزها بشكل متكرر.
• أكثر كفاءة من فرز الفقاعات وغيرها من الطرق البسيطة.

عملية:

• قيمة المقارنة (المحور):
• يتم اختيار قيمة كمرجع (محوري) ويتم تنظيم المصفوفة حول تلك القيمة.
• العناصر الأصغر من المحور تذهب إلى جانب والعناصر الأكبر إلى الجانب الآخر.
• يتم تكرار العملية بشكل متكرر لكل قسم حتى يتم فرز المصفوفة بالكامل.

فرز سريع

عرض QSD