أجهزة الكمبيوتربرمجة

فرز سريع كوسيلة من وسائل البرمجة

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

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

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

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

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

مرة واحدة يتم تحديد اختيار، يمكنك أن تنتقل إلى الخوارزمية التحلل. هذا ما يسمى الحلقات الداخلية نوع سريع. كل شيء مبني على مؤشرين الوصول السريع: اذهب أولا على عناصر من اليسار إلى اليمين، والثاني، على العكس من ذلك، من اليمين إلى اليسار. يبدأ حق تنفيذ العملية: مؤشر على قائمة ومقارنة كل القيم الرئيسية. دورة كاملة عندما يكون العنصر أقل من أو يساوي خط الأساس. وهذا هو، هناك مقارنة ويقلل من قيمة المؤشر. على اليد اليسرى عند الانتهاء من العمل أكبر من أو قيمة متساوية. هنا، ويزيد من قيمة المقارنة.

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

Similar articles

 

 

 

 

Trending Now

 

 

 

 

Newest

Copyright © 2018 ar.atomiyme.com. Theme powered by WordPress.