في عام 1960 ، K.A.طور Hoare طريقة لفرز المعلومات بسرعة ، والتي أصبحت الأكثر شهرة. اليوم يستخدم على نطاق واسع في البرمجة ، لأنه يحتوي على الكثير من الخصائص الإيجابية: يمكن استخدامه في الحالات العامة ، يتطلب زيادة صغيرة في الذاكرة الإضافية ، وهو متوافق مع أنواع مختلفة من القوائم وهو مناسب للتنفيذ. ولكن هناك أيضا عيوب أن الفرز السريع له: عند استخدامه في العمل ، يسمح العديد من الأخطاء وأنه غير مستقر إلى حد ما.
ومع ذلك ، هذه هي النسخة الأكثر درسًا.بعد ظهور حسابات هور الأولى ، شارك كثيرون في دراستها الكثيفة. تم إنشاء قاعدة كبيرة على الأسئلة النظرية لإيجاد الوقت المستغرق في العمل ، والذي تم دعمه بالبيانات التجريبية. كانت هناك اقتراحات حقيقية لتحسين الخوارزمية الرئيسية وزيادة سرعة العمل.
الفرز السريع شائع جدا ، يمكنك ذلكيجتمع في كل مكان. ويستند إلى طريقة TList.Sort ، التي توجد في جميع الإصدارات (باستثناء 1) من دلفي ، وظيفة المكتبة في الوقت المستغرق في التنفيذ ، qsort في C ++.
يمكن صياغة المبدأ الأساسي للعمل"فرق وقهر". هناك انهيار القائمة إلى مجموعتين ويتم إجراء الفرز لكل جزء من تلقاء نفسه. ويترتب على ذلك ضرورة إيلاء المزيد من الاهتمام بعملية الفصل ، التي يحدث خلالها ما يلي: يتم تحديد العنصر الأساسي وتحول القائمة بأكملها بالفعل بالنسبة لها. يتم تشكيل مجموعة من المرشحين إلى اليسار ، والقيم التي هي أصغر ، ويتم نقل جميع الآخرين إلى اليمين. وتبين أن العنصر الرئيسي في القائمة التي تم فرزها يقع في مكانه الصحيح. الخطوة التالية هي استدعاء دالة الفرز المتكرر لكلا جانبي العناصر المتعلقة بالقاعدة. تنتهي عملية العمل فقط عندما تحتوي القائمة على عنصر واحد فقط ، أي أنه سيتم فرزها. وهكذا ، من أجل إتقان وظيفة البرمجة مثل الفرز السريع ، تحتاج إلى معرفة تشغيل الخوارزميات ذات المستوى الأدنى: أ) اختيار العنصر الأساسي ؛ ب) أكثر تعشيق القائمة فعالية للحصول على مجموعتين بقيم أصغر وأكبر.
سنتعرف على مبادئ الأول.عند اختيار عنصر أساسي ، يجب اختيار الطبقة الوسطى من القائمة. ثم ، عندما يتم تقسيمها ، يتم تقسيمها إلى نصفين متساويين. فقط حساب متوسط القيمة في القائمة صعب للغاية ، لذلك حتى أسرع الفرز يتجاوز هذا حساب التفاضل والتكامل بالجانب. لكن اختيار العنصر الرئيسي بالقيمة القصوى أو الدنيا ليس هو أيضًا الخيار الأفضل. في حالة وجود مثل هذا التعريف ، سيتم ضمان أن تكون واحدة من القوائم التي تم إنشاؤها فارغة ، وتفيض الثانية. ومن هنا نستنتج أنه كعنصر أساسي ، يجب اختيار واحد أقرب إلى المتوسط ، ولكن أبعد من الحد الأقصى والأدنى.
بمجرد الانتهاء من اختيارك ، يمكنك ذلكانتقل إلى تشغيل خوارزمية التقسيم. هذه هي ما يسمى دورات فرز سريع الداخلية. كل شيء مبني على فهارسين سريع الأداء: الأول سوف يمر بالعناصر من اليسار إلى اليمين ، والثاني على العكس ، من اليمين إلى اليسار. تبدأ عملية التنفيذ على اليمين: يمر المؤشر بالقائمة ويقارن جميع القيم مع القيمة الرئيسية. تعتبر الدورة كاملة إذا كان هناك عنصر أقل من أو يساوي القاعدة. وهذا هو ، يحدث مقارنة وانخفاض قيمة الفهرس. على الجانب الأيسر ، يتم الانتهاء من العمل عند إيجاد قيمة أكبر أو مساوية. وهنا القيمة عند مقارنة الزيادات.
في هذه المرحلة من خوارزمية التقسيم ،الذي يحتوي على نوع سريع ، يمكن أن تنشأ حالتين. الأول هو أن المؤشر على اليسار سيكون أقل من اليمين. يشير هذا إلى وجود خطأ ، أي أن العناصر التي تم تحديدها لها في الترتيب غير الصحيح في القائمة. المخرج هو تغيير الأماكن. الحالة الثانية هي عندما يكون كلا الأعمدة متساويين أو متقاطعين. يشير هذا إلى تقسيم ناجح للقائمة ، أي يمكن اعتبار العمل مكتملاً.
