ترتيب سريع: الفرق بين النسختين

تم إضافة 38 بايت ، ‏ قبل شهرين
مِيزة اقتراح الروابط: تمت إضافة 4 روابط.
(مِيزة اقتراح الروابط: تمت إضافة 4 روابط.)
 
 
== تاريخ ==
تم تطوير خوارزمية الفرز السريع في عام 1959 من قبل [[توني هور]] عندما كان طالبًا زائرًا في [[جامعة موسكو الحكومية]] . في ذلك الوقت، كان هور يعمل على مشروع [[ترجمة آلية]] [[المختبر الفيزيائي الوطني (المملكة المتحدة)|للمختبر الفيزيائي الوطني]] . كجزء من عملية الترجمة، كان بحاجة إلى فرز الكلمات في الجمل الروسية قبل البحث عنها في قاموس روسي إنجليزي، والذي كان بالترتيب الأبجدي على [[تخزين بيانات الشريط المغناطيسي|شريط مغناطيسي]] . <ref>{{استشهاد بدورية محكمة|الأخير=Shustek|الأول=L.|عنوان=Interview: An interview with C.A.R. Hoare|DOI=10.1145/1467247.1467261|صحيفة=[[Communications of the ACM|Comm. ACM]]|المجلد=52|العدد=3|صفحات=38–41|سنة=2009}}</ref> بعد أن أدرك أن فكرته الأولى، [[ترتيب بالإدراج|نوع الإدراج]]، ستكون بطيئة، توصل إلى فكرة جديدة. لقد كتب جزء القسم في ميركوري [[أوتوكود]] ولكنه واجه مشكلة في التعامل مع قائمة المقاطع التي لم يتم فرزها. عند العودة إلى إنجلترا، طُلب منه كتابة رمز لـ [[الترتيب]]. ذكر هور لرئيسه أنه يعرف خوارزمية أسرع وراهن رئيسه بستة بنسات على أنه لم يعرفها. وافق رئيسه في النهاية على أنه خسر الرهان. في وقت لاحق، تعلم هور عن [[ألغول (لغة برمجة)|لغة ألغول للبرمجة]] وقدرته على القيام بالعودة التي مكنته من نشر الكود في مجلة علوم الاتصالات وآلات الحوسبة ([[اللغة الإنجليزية|بالإنجليزية]]: Communications of the Association for Computing Machinery)، وهي مجلة [[علم الحاسوب|علوم الكمبيوتر]] الأولى في ذلك الوقت. <ref name="alg64" /> <ref>{{استشهاد ويب
| مسار = http://anothercasualcoder.blogspot.com/2015/03/my-quickshort-interview-with-sir-tony.html
| عنوان = My Quickshort interview with Sir Tony Hoare, the inventor of Quicksort
 
=== تحسينات أخرى ===
عند استعمال الترتيب السريع لترتيب مجموعة ذات عناصر كبيرة، يمكن تغيير تقنية الترتيب عند الوصول إلى [[مجموعة جزئية]] غير مرتبة عدد عناصرها صغير،10 أو أقل. الترتيب بالاختيار مناسب في هذه الحالة.
 
== الخوارزمية ==
[[شجرة بحث ثنائية|تتوافق شجرة البحث الثنائية]] التالية (BST) مع كل تنفيذ للفرز السريع: المحور الأولي هو العقدة الجذرية ؛ محور النصف الأيسر هو جذر الشجرة الفرعية اليسرى، ومحور النصف الأيمن هو جذر الشجرة الفرعية اليمنى، وهكذا. عدد مقارنات تنفيذ الفرز السريع يساوي عدد المقارنات أثناء إنشاء BST من خلال سلسلة من عمليات الإدراج. لذا، فإن متوسط عدد المقارنات للفرز السريع العشوائي يساوي متوسط تكلفة إنشاء BST عند إدراج القيم <math>(x_1,x_2,\ldots,x_n)</math> تشكيل تبديل عشوائي.
 
ضع في اعتبارك BST تم إنشاؤه عن طريق إدراج تسلسل <math>(x_1,x_2,\ldots,x_n)</math> من القيم التي تشكل التقليب العشوائي. دع {{Mvar|C}} تشير إلى تكلفة إنشاء BST. نملك <math>C=\sum_i \sum_{j<i} c_{i,j}</math>، أين <math>c_{i,j}</math> هو [[متغير عشوائي]] ثنائي يعبر عما إذا كان أثناء إدخال <math>x_i</math> كانت هناك مقارنة <math>x_j</math> .
 
حسب [[قيمة متوقعة|خطية التوقع]]، القيمة المتوقعة <math>\operatorname{E}[C]</math> من {{Mvar|C}} هو <math>\operatorname{E}[C]= \sum_i \sum_{j<i} \Pr(c_{i,j})</math> .
ترتيب سريع مع التقسيم الموضعي وغير المستقر يستخدم مساحة إضافية ثابتة فقط قبل إجراء أي مكالمة متكررة. يجب أن يقوم ترتيب سريع بتخزين قدر ثابت من المعلومات لكل مكالمة متكررة متداخلة. نظرًا لأن أفضل حالة تجعل على الأكثر استدعاءات متكررة متداخلة {{تعبير رياضي|''O''(log ''n'')}}، فإنها تستخدم مساحة {{تعبير رياضي|''O''(log ''n'')}} ومع ذلك، من دون حيلة سيدجويك للحد من المكالمات متكررة، في أسوأ حالة فرز سريع يمكن أن تجعل {{تعبير رياضي|''O''(''n'')}} دعوات متكررة متداخلة والحاجة {{تعبير رياضي|''O''(''n'')}} الفضاء مساعدة.
 
من وجهة نظر التعقيد قليلاً، ''لا تستخدم المتغيرات مثل lo'' و ''hi'' مساحة ثابتة ؛ يستغرق الأمر {{تعبير رياضي|''O''(log ''n'')}} bits للفهرسة في قائمة {{Mvar|n}} من العناصر. نظرًا لوجود مثل هذه المتغيرات في كل إطار مكدس، فإن الترتيب السريع باستخدام خدعة وبرت سيدجويك يتطلب {{تعبير رياضي|''O''((log ''n'')²)}} [[بت]] من المساحة. متطلبات المساحة هذه ليست سيئة للغاية، على الرغم من ذلك، لأنه إذا كانت القائمة تحتوي على عناصر مميزة، فستحتاج على الأقل إلى {{تعبير رياضي|''O''(''n'' log ''n'')}} بت من المساحة.
 
إصدار آخر، أقل شيوعًا، غير موجود، من الترتيب السريع يستخدم {{تعبير رياضي|''O''(''n'')}} لتخزين العمل ويمكنه تنفيذ فرز مستقر. تسمح مساحة التخزين العاملة بتقسيم مصفوفة الإدخال بسهولة بطريقة مستقرة ثم نسخها مرة أخرى إلى مصفوفة الإدخال لإجراء مكالمات متكررة متتالية. لا يزال تحسين روبرت سيدجويك مناسبًا.