عرض مصدر ترتيب سريع

{{بطاقة خوارزمية
|image=Sorting quicksort anim.gif
|caption=تصور متحرك لخوارزمية الفرز السريع. الخطوط الأفقية هي قيم محورية.}}

'''الترتيب السريع''' ([[اللغة الإنجليزية|بالإنجليزية]]: Quicksort) هي [[خوارزمية]] لترتيب المصفوفات (تصاعديّا أو تنازليّا) من ابتكار [[إنجلترا|الإنجليزي]] [[توني هور]] في [[1961]].<ref>[http://www.cs.columbia.edu/~hgs/teaching/isp/hw/qsort.c ], [http://repo.or.cz/w/glibc.git/blob/HEAD:/stdlib/qsort.c] {{Webarchive|url=https://web.archive.org/web/20171023194926/http://www.cs.columbia.edu/~hgs/teaching/isp/hw/qsort.c |date=23 أكتوبر 2017}}</ref><ref>{{استشهاد بدورية محكمة | الأخير1 = Sedgewick | الأول1 = R. | مؤلف1-وصلة = Robert Sedgewick (computer scientist) | عنوان = Implementing Quicksort programs | doi = 10.1145/359619.359631 | صحيفة = {{Ill-WD2|Comm. ACM|id=Q1120519}} | المجلد = 21 | العدد = 10 | صفحات = 847–857 | سنة = 1978 | pmid = | pmc = }}</ref><ref>{{استشهاد بويب | عنوان=Sir Antony Hoare | ناشر=Computer History Museum | تاريخ الوصول=22 April 2015 | مسار=https://www.computerhistory.org/fellowawards/hall/bios/Antony,Hoare/ | وصلة مكسورة=yes | مسار أرشيف=https://web.archive.org/web/20150403184558/http://www.computerhistory.org/fellowawards/hall/bios/Antony%2CHoare/ | تاريخ أرشيف=3 April 2015 | df=dmy-all }}</ref><ref>[https://cs.stanford.edu/people/eroberts/courses/soco/projects/2008-09/tony-hoare/quicksort.html الترتيب السريع لشارلس أنطوني هاور] {{Webarchive|url=https://web.archive.org/web/20160422132251/http://cs.stanford.edu/people/eroberts/courses/soco/projects/2008-09/tony-hoare/quicksort.html |date=22 أبريل 2016}}</ref>

'''ترتيب سريع''' هي [[خوارزمية ترتيب|خوارزمية فرز]] [[كفاءة خوارزمية|فعالة]]. تم تطويره بواسطة [[عالم حاسوب|عالم الكمبيوتر]] البريطاني [[توني هور]] في عام 1959 <ref>{{استشهاد بويب
| مسار = http://www.computerhistory.org/fellowawards/hall/bios/Antony,Hoare/
| عنوان = Sir Antony Hoare
| ناشر = Computer History Museum
| مسار أرشيف = https://web.archive.org/web/20150403184558/http://www.computerhistory.org/fellowawards/hall/bios/Antony%2CHoare/
| تاريخ أرشيف = 3 April 2015
| تاريخ الوصول = 22 April 2015
}}</ref> ونشر في عام 1961، <ref name="alg64">{{استشهاد بدورية محكمة|الأخير=Hoare|الأول=C. A. R.|عنوان=Algorithm 64: Quicksort|DOI=10.1145/366622.366644|صحيفة={{Ill-WD2|Comm. ACM|id=Q1120519}}|المجلد=4|العدد=7|صفحات=321|سنة=1961}}</ref> ولا يزال خوارزمية الفرز شائعة الاستخدام. عندما يتم تنفيذه بشكل جيد، يمكن أن يكون أسرع إلى حد ما من [[تصنيف دمجي|دمج الفرز]] وحوالي مرتين أو ثلاث مرات أسرع من [[تصنيف الكومة|فرز الكومة]].<ref name="skiena">{{استشهاد بكتاب|الأول=Steven S.|مؤلف1=Skiena|سنة=2008|مؤلف-وصلة=Steven Skiena|عنوان=The Algorithm Design Manual|مسار=https://books.google.com/books?id=7XUSn0IKQEgC|ناشر=Springer|ISBN=978-1-84800-069-8|صفحة=129| مسار أرشيف = https://web.archive.org/web/20190805063437/http://books.google.com/books?id=7XUSn0IKQEgC | تاريخ أرشيف = 5 أغسطس 2019 }}</ref>

الترتيب السريع هو خوارزمية [[خوارزمية فرق تسد|فرق تسد]]. إنه يعمل عن طريق تحديد عنصر «محوري» من المصفوفة وتقسيم العناصر الأخرى إلى مصفوفتين فرعيتين، وفقًا لما إذا كانت أقل من المحور أو أكبر منه. لهذا السبب، يطلق عليه أحيانًا '''فرز تبادل الأقسام'''.<ref>C.L. Foster, ''Algorithms, Abstraction and Implementation'', 1992, {{ردمك|0122626605}}, p. 98</ref> ثم يتم فرز المصفوفات الفرعية [[عودية (علم الحاسوب)|بشكل متكرر]]. يمكن القيام بذلك [[خوارزمية موضعية|في نفس المكان]]، مما يتطلب مساحات إضافية صغيرة من [[تخزين بيانات الحاسوب|الذاكرة]] لإجراء الفرز.

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

[[تحليل الخوارزميات|يُظهر التحليل الرياضي]] للفرز السريع أن [[حالة سلوك خوارزمية|الخوارزمية، في المتوسط]]، تأخذ [[تمثيل O الكبرى|O]] (''n''&nbsp;سجل&nbsp;''ن'') مقارنات لفرز ''ن'' العناصر. في [[حالة سلوك خوارزمية|أسوأ الحالات]]، تقوم بإجراء ''مقارنات O (n'' <sup>2</sup>)، على الرغم من أن هذا السلوك نادر.

== تاريخ ==
تم تطوير خوارزمية الفرز السريع في عام 1959 من قبل [[توني هور]] عندما كان طالبًا زائرًا في [[جامعة موسكو الحكومية]]. في ذلك الوقت، كان هور يعمل على مشروع [[ترجمة آلية]] [[المختبر الفيزيائي الوطني (المملكة المتحدة)|للمختبر الفيزيائي الوطني]]. كجزء من عملية الترجمة، كان بحاجة إلى فرز الكلمات في الجمل الروسية قبل البحث عنها في قاموس روسي إنجليزي، والذي كان بالترتيب الأبجدي على [[تخزين بيانات الشريط المغناطيسي|شريط مغناطيسي]].<ref>{{استشهاد بدورية محكمة|الأخير=Shustek|الأول=L.|عنوان=Interview: An interview with C.A.R. Hoare|DOI=10.1145/1467247.1467261|صحيفة={{Ill-WD2|Comm. ACM|id=Q1120519}}|المجلد=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
| تاريخ = 2015-03-15
| ناشر = Marcelo M De Barros
| مسار أرشيف = https://web.archive.org/web/20200607211307/https://anothercasualcoder.blogspot.com/2015/03/my-quickshort-interview-with-sir-tony.html | تاريخ أرشيف = 7 يونيو 2020 }}</ref>

اكتسب ترتيب سريع اعتمادًا واسع النطاق، حيث ظهر، على سبيل المثال، في [[يونكس]] باعتباره روتين فرعي افتراضي لفرز المكتبة. ومن ثم، أعار اسمها إلى الروتين الفرعي [[مكتبة سي المعيارية|للمكتبة القياسية C.]]{{مونو|[[دالة qsort]]}} <ref name="engineering">{{استشهاد بدورية محكمة|الأول=Jon L.|الأخير=Bentley|الأول2=M. Douglas|الأخير2=McIlroy|عنوان=Engineering a sort function|صحيفة=Software—Practice and Experience|المجلد=23|العدد=11|صفحات=1249–1265|سنة=1993|مسار=http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8162|DOI=10.1002/spe.4380231105| مسار أرشيف = https://web.archive.org/web/20200803212253/http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.8162 | تاريخ أرشيف = 3 أغسطس 2020 }}</ref> وفي تنفيذ المرجع [[جافا (لغة برمجة)|لجافا]].

[[روبرت سيدجويك (عالم كمبيوتر)|تعتبر أطروحة الدكتوراه لروبرت سيدجويك]] في عام 1975 علامة فارقة في دراسة ترتيب سريع حيث قام بحل العديد من المشكلات المفتوحة المتعلقة بتحليل مخططات الاختيار المحوري المختلفة بما في ذلك [[عينات|العينات]] والتقسيم التكيفي بواسطة فان إمدن <ref>{{استشهاد بدورية محكمة|عنوان=Algorithms 402: Increasing the Efficiency of Quicksort|صحيفة=Commun. ACM|تاريخ=1970-11-01|issn=0001-0782|صفحات=693–694|المجلد=13|العدد=11|DOI=10.1145/362790.362803|الأول=M. H.|الأخير=Van Emden}}</ref> بالإضافة إلى اشتقاق العدد المتوقع المقارنات والمقايضات.<ref name="engineering" /> [[جون بنتلي (عالم حاسوب)|قام جون بنتلي]] [[دوغلاس ماكلروي|ودوغ ماكلروي]] بدمج تحسينات مختلفة للاستخدام في مكتبات البرمجة، بما في ذلك تقنية للتعامل مع العناصر المتساوية والمخطط المحوري المعروف باسم ''pseudomedian of تسعة،'' حيث يتم تقسيم عينة من تسعة عناصر إلى مجموعات من ثلاثة ثم متوسط يتم اختيار ثلاثة وسطاء من ثلاث مجموعات.<ref name="engineering" /> وصف بنتلي مخطط تقسيم آخر أبسط ومضغوط في كتابه ''لآلئ البرمجة'' التي نسبها إلى نيكو لوموتو. كتب بنتلي لاحقًا أنه استخدم نسخة هور لسنوات لكنه لم يفهمها أبدًا، لكن نسخة لوموتو كانت بسيطة بما يكفي لإثبات صحتها.<ref>{{استشهاد بكتاب|عنوان=Beautiful Code: Leading Programmers Explain How They Think|مسار=https://archive.org/details/beautifulcodelea00oram_950|محرر1=Oram|محرر1-الأول=Andy|محرر2=Wilson|محرر2-الأول=Greg|ناشر=O'Reilly Media|سنة=2007|ISBN=978-0-596-51004-6|صفحات=[https://archive.org/details/beautifulcodelea00oram_950/page/n52 30]|الفصل=The most beautiful code I never wrote|الأول=Jon|مؤلف1=Bentley|مؤلف-وصلة=Jon Bentley (computer scientist)}}</ref> وصفت بنتلي ترتيب سريع بأنها «أجمل رمز كتبته على الإطلاق» في نفس المقال. تم أيضًا تعميم مخطط تقسيم لوموتو من خلال ''[[مقدمة في الخوارزميات (كتاب)|مقدمة]]'' الكتاب المدرسي للخوارزميات على الرغم من أنه أدنى من مخطط هور لأنه يقوم {{تعبير رياضي|''O''(''n''<sup>2</sup>)}} وقت التشغيل عندما تكون جميع العناصر متساوية.<ref name=":1">{{استشهاد بويب
| مسار = https://cs.stackexchange.com/q/11550
| عنوان = Quicksort Partitioning: Hoare vs. Lomuto
| موقع = cs.stackexchange.com
| تاريخ الوصول = 2015-08-03
| مسار أرشيف = https://web.archive.org/web/20190811203857/https://cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto/11550#11550 | تاريخ أرشيف = 11 أغسطس 2019 }}</ref>  <sup class="noprint Inline-Template" style="white-space:nowrap;">&#x5D;</sup>

في عام 2009، اقترح فلاديمير ياروسلافسكي تطبيق ترتيب سريع جديدًا باستخدام محورين بدلاً من واحد.<ref name=":0">{{استشهاد بويب
| مسار = http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
| عنوان = Dual-Pivot Quicksort
| تاريخ = 2009
| مسار أرشيف = https://web.archive.org/web/20151002230717/http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
| تاريخ أرشيف = 2015-10-02
| الأخير = Yaroslavskiy
| الأول = Vladimir
}}</ref> في القوائم البريدية لمكتبة جافا الأساسية، بدأ نقاشًا يدعي فيه أن خوارزميته الجديدة متفوقة على طريقة فرز مكتبة وقت التشغيل، والتي كانت تعتمد في ذلك الوقت على المتغير المستخدم على نطاق واسع والمضبوط بعناية من ترتيب سريع الكلاسيكي بواسطة بنتلي وماكلروي.<ref>{{استشهاد بويب
| مسار = http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
| عنوان = Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quick
| موقع = permalink.gmane.org
| تاريخ الوصول = 2015-08-03
|مسار أرشيف= https://web.archive.org/web/20181106225449/http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
|تاريخ أرشيف=2018-11-06}}</ref> تم اختيار الترتيب السريع لـ ياروسلافسكي كخوارزمية فرز افتراضية جديدة في مكتبة وقت تشغيل جافا 7 من أوراكل <ref>{{استشهاد بويب
| مسار = https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(int[])
| عنوان = Java 7 Arrays API documentation
| ناشر = Oracle
| تاريخ الوصول = 2018-07-23
|مسار أرشيف= https://web.archive.org/web/20201112040249/https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html
|تاريخ أرشيف=2020-11-12}}</ref> بعد اختبارات أداء تجريبية مكثفة.<ref>{{استشهاد بكتاب|عنوان=Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn|ناشر=Society for Industrial and Applied Mathematics|تاريخ=2013-01-07|ISBN=978-1-61197-253-5|صفحات=55–69|سلسلة=Proceedings|DOI=10.1137/1.9781611972931.5|الأول=S.|مؤلف1=Wild|الأول2=M.|مؤلف2=Nebel|الأول3=R.|الأخير3=Reitzig|الأول4=U.|الأخير4=Laube}}</ref>

== عن التفضيلات والخوارزمية ==
تنبني الخوارزمية على وضع العنصر الأول في المصفوفة (بإتخاذه محورًا), ثم ترتيب ووضع العناصر الأكبر من هذا المحور إلى جهة اليمنى من المصفوفة ووضع العناصر الأصغر في الجهة اليسرى. بهذه الطريقة يعتبر المحور في مكانه النهائي المرتّب. تسمى هذه العملية تجزئة ليتبقى من المصفوفة جزئين لم يتم ترتيبهما. نقوم بعد ذلك بإعادة هذه الطريقة على الجزئين المتبقيين من المصفوفة وهكذا نحدد محورا جديدا ونعيد عملية التجزئة. تتكرر هذه العملية إلى أن نحصل على مجموعة مرتبة.

إذا تم اختيار المحور بطريقة صحيحة، نحصل على الطريقة الأسرع للترتيب في الحالة المتوسطة، مع تعقيد ب<math>\Theta(n\log n)</math>. والتي قد تتحول إلى <math>\Theta(n^2)</math> في الحالة الأصعب، وهي حالة جدول عناصره مرتبة أصلا. ولكن هذه الحالة بديهية لأن المجموعة مرتبة أصلا.

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

و بصفة عامة يعتبر الترتيب السريع الأكثر شيوعا (شعبية) من بين جميع خوارزميات الترتيب.

المشكلة الوحيدة تتمثل في كيفية اختيار المحور.
=== اختيار أفضل مؤشر ===
عند استعمال الترتيب السريع لمجموعة مرتبة مسبقا، وبطريقة اعتباطية، يستغرق كما قلنا وقتا كبيرا، وذلك راجع لأن أول عنصر هو الذي يعتبر محورا، الشيء الذي يؤدي إلى عدم تقسيم المجموعة إلى قسمين أكبر وأصغر من المحور. لحل المشكل يتم اختيار العنصر الأوسط، كما يمكن اختياره عشوائيا من عنصرين متواجدين حول المركز، حيث أن عملية اختيار المحور أو الأساس تحدد أداء الخوارزمية وتأرجحها بين وقت التشغيل N*Log n وN^<sup>2 بصيغة Big O Notation.

=== تحسينات أخرى ===
عند استعمال الترتيب السريع لترتيب مجموعة ذات عناصر كبيرة، يمكن تغيير تقنية الترتيب عند الوصول إلى [[مجموعة جزئية]] غير مرتبة عدد عناصرها صغير،10 أو أقل. الترتيب بالاختيار مناسب في هذه الحالة.

== الخوارزمية ==
[[ملف:Quicksort-diagram.svg|يسار|تصغير|400x400بك|مثال كامل للفرز السريع على مجموعة عشوائية من الأرقام. العنصر المظلل هو المحور. يتم اختياره دائمًا كعنصر أخير في القسم. ومع ذلك، دائمًا ما يؤدي اختيار العنصر الأخير في القسم كمحور بهذه الطريقة إلى أداء ضعيف ( {{تعبير رياضي|''O''(''n''²)}} ) في ''المصفوفات التي تم فرزها بالفعل'' أو صفائف العناصر المتطابقة. نظرًا لأن المصفوفات الفرعية للعناصر المصنفة / المتطابقة تظهر كثيرًا في نهاية إجراء الفرز على مجموعة كبيرة، فإن إصدارات خوارزمية الفرز السريع التي تختار المحور كعنصر متوسط تعمل بسرعة أكبر بكثير من الخوارزمية الموضحة في هذا الرسم البياني على مجموعات كبيرة من الأرقام.]]
ترتيب سريع هي [[خوارزمية فرق تسد]]. يقوم أولاً بتقسيم مصفوفة الإدخال إلى مصفوفتين فرعيتين أصغر: العناصر المنخفضة والعناصر العالية. ثم يقوم بفرز المصفوفات الفرعية بشكل متكرر. خطوات [[خوارزمية موضعية|الترتيب]] السريع الموضعي هي:

# اختر عنصرًا يسمى ''المحور'' من المصفوفة.
# ''التقسيم'' : أعد ترتيب المصفوفة بحيث تأتي جميع العناصر ذات القيم الأقل من المحور قبل المحور، بينما تأتي جميع العناصر ذات القيم الأكبر من المحور بعده (يمكن أن تذهب القيم المتساوية في أي اتجاه). بعد هذا التقسيم، يكون المحور في موضعه النهائي. هذا يسمى عملية ''التقسيم'' .
# [[عودية (علم الحاسوب)|قم]] بتطبيق الخطوات المذكورة أعلاه بشكل متكرر على المصفوفة الفرعية للعناصر ذات القيم الأصغر وبشكل منفصل على المصفوفة الفرعية للعناصر ذات القيم الأكبر.

الحالة الأساسية للتكرار هي مصفوفات بحجم صفر أو واحد، وهي مرتبة حسب التعريف، لذلك لا تحتاج أبدًا إلى الفرز.

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

=== مخطط تقسيم لوموتو ===
يُنسب هذا المخطط إلى نيكو لوموتو وشاعه بنتلي في كتابه ''برمجة بيرلز وكورمين وآخرون.<ref name=":3">{{استشهاد بكتاب|مؤلف1=Jon Bentley|عنوان=Programming Pearls|ناشر=Addison-Wesley Professional|سنة=1999}}</ref>'' في كتابهم ''[[مقدمة في الخوارزميات (كتاب)|مقدمة في الخوارزميات]]''.<ref name=":2">{{Introduction to Algorithms|3|chapter=Quicksort|pages=170–190}}</ref> يختار هذا النظام المحور الذي يكون عادةً العنصر الأخير في المصفوفة. الخوارزمية تحتفظ بالفهرس{{مونو|i}} لأنه يمسح المصفوفة باستخدام فهرس آخر{{مونو|j}} مثل أن العناصر الموجودة في{{مونو|lo}} خلال الصغرى{{مونو|i-1}} (شامل) أقل من المحور والعناصر الموجودة في{{مونو|i}} خلال{{مونو|j}} (شاملة) تساوي أو أكبر من المحور. نظرًا لأن هذا المخطط أكثر إحكاما وسهل الفهم، فإنه يستخدم بشكل متكرر في المواد التمهيدية، على الرغم من أنه أقل كفاءة من مخطط هور الأصلي، على سبيل المثال، عندما تكون جميع العناصر متساوية.<ref>{{استشهاد بويب
| مسار = https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3463
| عنوان = Java 7's Dual Pivot Quicksort
| تاريخ = 2012
| ناشر = Technische Universität Kaiserslautern
| الأخير = Wild
| الأول = Sebastian
| مسار أرشيف = https://web.archive.org/web/20200727152253/https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3463 | تاريخ أرشيف = 27 يوليو 2020 }}</ref> يتحلل هذا المخطط إلى {{تعبير رياضي|''O''(''n''<sup>2</sup>)}} عندما تكون الصفيف في حالة جيدة بالفعل.<ref name=":1" /> كانت هناك متغيرات مختلفة مقترحة لتعزيز الأداء بما في ذلك طرق مختلفة لتحديد المحور، والتعامل مع العناصر المتساوية، واستخدام خوارزميات الفرز الأخرى مثل تصنيف [[ترتيب بالإدراج|الإدراج]] للمصفوفات الصغيرة وما إلى ذلك. في [[سودوكود]]، وهو تصنيف سريع يقوم بفرز العناصر في{{مونو|lo}} خلال الصغرى{{مونو|hi}} (شامل) للمصفوفة {{Mvar|A}} على النحو التالي:<ref name=":2" /><syntaxhighlight lang="logtalk">
algorithm quicksort(A, lo, hi) is
  if lo < hi then
     p := partition(A, lo, hi)
    quicksort(A, lo, p - 1)
    quicksort(A, p + 1, hi)
algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi do 
     if A[j] < pivot then
       swap A[i] with A[j] 
       i := i + 1 
swap A[i] with A[hi]
return i
</syntaxhighlight>يتم فرز المجموعة بأكملها بواسطة{{مونو|quicksort(A, 0, length(A) - 1)}} .

=== مخطط تقسيم هور ===
يستخدم مخطط التقسيم الأصلي الذي وصفه [[توني هور]] مؤشرين يبدأان في نهايات المصفوفة التي يتم تقسيمها، ثم ينتقلان باتجاه بعضهما البعض، حتى يكتشفوا انعكاسًا: زوج من العناصر، واحد أكبر من أو يساوي المحور، واحد أقل من أو يساوي، بترتيب خاطئ بالنسبة لبعضها البعض. ثم يتم تبديل العناصر المقلوبة.<ref>{{استشهاد بدورية محكمة|عنوان=Quicksort|مسار= http://comjnl.oxfordjournals.org/content/5/1/10|صحيفة=The Computer Journal|تاريخ=1962-01-01|issn=0010-4620|صفحات=10–16|المجلد=5|العدد=1|DOI=10.1093/comjnl/5.1.10|الأول=C. A. R.|الأخير=Hoare|مؤلف-وصلة=Tony Hoare|مسار أرشيف= https://web.archive.org/web/20140522044456/http://comjnl.oxfordjournals.org:80/content/5/1/10
|تاريخ أرشيف=2014-05-22}}</ref> عندما تلتقي المؤشرات، تتوقف الخوارزمية وتعيد الفهرس النهائي. يعتبر مخطط هور أكثر كفاءة من مخطط تقسيم لوموتو لأنه يقوم بإجراء مقايضات أقل بثلاث مرات في المتوسط، كما أنه ينشئ أقسامًا فعالة حتى عندما تكون جميع القيم متساوية.<ref name=":1" />  <sup class="noprint Inline-Template" style="white-space:nowrap;">&#x5D;</sup> مثل مخطط تقسيم لوموتو، سيؤدي تقسيم هور أيضًا إلى تدهور ترتيب سريع إلى {{تعبير رياضي|''O''(''n''<sup>2</sup>)}} للمدخلات التي تم فرزها بالفعل، إذا تم اختيار المحور ليكون العنصر الأول أو الأخير. مع وجود العنصر الأوسط كمحور، ينتج عن البيانات المصنفة (تقريبًا) عدم وجود مقايضات في أقسام متساوية الحجم تؤدي إلى أفضل سلوك حالة لـ ترتيب سريع، أي {{تعبير رياضي|''O''(''n'' log(''n''))}} . مثل الآخرين، لا ينتج تقسيم هور نوعًا مستقرًا. في هذا المخطط، لا يكون الموقع النهائي للمحور بالضرورة في الفهرس الذي يتم إرجاعه، حيث يمكن أن ينتهي المحور والعناصر التي تساوي المحور في أي مكان داخل القسم بعد خطوة القسم، وقد لا يتم فرزها حتى الحالة الأساسية لـ يتم الوصول إلى القسم الذي يحتوي على عنصر واحد عبر العودية. المقطعان التاليان اللذان تكررهما الخوارزمية الرئيسية هما{{مونو|(lo..p)}} (العناصر ≤ المحور) و{{مونو|(p+1..hi)}} (العناصر ≥ المحور) مقابل{{مونو|(lo..p-1)}} و{{مونو|(p+1..hi)}} كما في مخطط لوموتو. ومع ذلك، فإن خوارزمية التقسيم تضمن {{بدون لف|{{مونو|lo ≤ p < hi}}}} مما يعني أن كلا القسمين الناتجين غير فارغين، وبالتالي لا يوجد خطر من التكرار اللانهائي. في [[سودوكود|الكود الزائف]]، <ref name=":2" /><syntaxhighlight lang="logos">
algorithm quicksort(A, lo, hi) is
   if lo < hi then
      p := partition(A, lo, hi)
    quicksort(A, lo, p) 
    quicksort(A, p + 1, hi) 
algorithm partition(A, lo, hi) is
    pivot := A[ floor((hi + lo) / 2) ]
    i := lo - 1
    j := hi + 1
    loop forever 
      do
        i := i + 1 
      while A[i] < pivot do 
        j := j - 1 
      while A[j] > pivot
   if i ≥ j then 
      return j
   swap A[i] with A[j]
</syntaxhighlight>يتم تقريب التقسيم المحوري لأسفل، كما هو موضح هنا بواسطة دالة <kbd>الأرضية؛</kbd> <ref>in many languages this is the standard behavior of integer division</ref> هذا يتجنب استخدام A [hi] كمحور، مما قد يؤدي إلى تكرار لا نهائي.

يتم فرز المجموعة بأكملها حسب{{مونو|quicksort(A, 0, length(A) - 1)}} .

=== قضايا التنفيذ ===

==== اختيار المحور ====
في الإصدارات المبكرة جدًا من الترتيب السريع، غالبًا ما يتم اختيار العنصر الموجود في أقصى اليسار كعنصر محوري. لسوء الحظ، يتسبب هذا في سلوك أسوأ حالة على المصفوفات التي تم فرزها بالفعل، وهي حالة استخدام شائعة إلى حد ما. تم حل المشكلة بسهولة عن طريق اختيار إما فهرس عشوائي للمحور، أو اختيار المؤشر الأوسط للقسم أو (خاصة للأقسام الأطول) باختيار [[وسيط (إحصاء)|وسيط]] العنصر الأول والمتوسط والأخير من القسم للمحور (على النحو الموصى به من قبل [[روبرت سيدجويك (عالم كمبيوتر)|عالم الكمبيوتر]] [[روبرت سيدجويك (عالم كمبيوتر)|روبرت سيدجويك]]).<ref name="sedgewickBook">{{استشهاد بكتاب|مؤلف1=Sedgewick|الأول=Robert|مؤلف-وصلة=Robert Sedgewick (computer scientist)|عنوان=Algorithms in C: Fundamentals, Data Structures, Sorting, Searching, Parts 1–4|مسار= https://books.google.com/books?id=ylAETlep0CwC|طبعة=3|تاريخ=1 September 1998|ناشر=Pearson Education|ISBN=978-81-317-1291-7|مسار أرشيف= https://web.archive.org/web/20200820030743/https://books.google.com/books?id=ylAETlep0CwC
|تاريخ أرشيف=2020-08-20}}</ref> تقاوم قاعدة «الوسيط من ثلاثة» حالة الإدخال المصنف (أو الفرز العكسي)، وتعطي تقديرًا أفضل للمحور الأمثل (الوسيط الحقيقي) بدلاً من تحديد أي عنصر فردي، في حالة عدم وجود معلومات حول ترتيب الإدخال معروف.

مقتطف رمز متوسط من ثلاثة لقسم لوموتو:<syntaxhighlight lang="logtalk">
mid := ⌊(lo + hi) / 2
⌋ if A[mid] < A[lo]
  swap A[lo] with A[mid]
if A[hi] < A[lo]
  swap A[lo] with A[hi] 
if A[mid] < A[hi]
  swap A[mid] with A[hi]
pivot := A[hi]
</syntaxhighlight>يضع الوسيط في <code>A[hi]</code> أولاً، ثم يتم استخدام القيمة الجديدة لـ <code>A[hi]</code> للمحور، كما هو الحال في الخوارزمية الأساسية المعروضة أعلاه.

على وجه التحديد، العدد المتوقع من المقارنات اللازمة لفرز {{Mvar|n}} العناصر (انظر {{وصلة قسم||تحليل الفرز السريع العشوائي}}) مع الاختيار المحوري العشوائي هو {{تعبير رياضي|1.386 ''n'' log ''n''}} . يؤدي متوسط ثلاثة محاور إلى خفض هذا إلى {{تعبير رياضي|[[معامل ذات الحدين|معامل ذو الحدين]]<sub>''n'', 2</sub> ≈ 1.188 ''n'' log ''n''}}، على حساب زيادة قدرها ثلاثة بالمائة في العدد المتوقع من المقايضات. {{استشهاد متعدد|engineering}} قاعدة تمحور أقوى، للمصفوفات الأكبر، هي اختيار [[وسيط (إحصاء)|التاسع]]، وهو متوسط تكراري من ثلاثة (Mo3)، كما هو محدد. {{استشهاد متعدد|engineering}}

{{تعبير رياضي|ninther(''a'') {{=}} median(Mo3(first ⅓ of ''a''), Mo3(middle ⅓ of ''a''), Mo3(final ⅓ of ''a''))}}

يعد تحديد عنصر محوري أمرًا معقدًا أيضًا بسبب وجود [[طفح عدد صحيح|تجاوز عدد صحيح]]. إذا كانت مؤشرات الحدود للمصفوفة الفرعية التي يتم فرزها كبيرة بدرجة كافية، فإن التعبير الساذج للفهرس الأوسط، {{تعبير رياضي|(''lo'' + ''hi'')/2}}، سيؤدي إلى تجاوز التدفق وتوفير فهرس محوري غير صالح. يمكن التغلب على ذلك باستخدام، على سبيل المثال، {{تعبير رياضي|''lo'' + (''hi''−''lo'')/2}} لفهرسة العنصر الأوسط، على حساب حسابي أكثر تعقيدًا. تظهر مشكلات مماثلة في بعض الطرق الأخرى لاختيار العنصر المحوري.

==== عناصر متكررة ====
باستخدام خوارزمية التقسيم مثل مخطط تقسيم لوموتو الموضح أعلاه (حتى إذا كان يختار قيمًا محورية جيدة)، يُظهر الترتيب السريع أداءً ضعيفًا للمدخلات التي تحتوي على العديد من العناصر المتكررة. تظهر المشكلة بوضوح عندما تكون جميع عناصر الإدخال متساوية: في كل تكرار، يكون القسم الأيسر فارغًا (لا توجد قيم إدخال أقل من المحور)، ويكون القسم الأيمن قد انخفض بمقدار عنصر واحد فقط (تتم إزالة المحور). وبالتالي، فإن مخطط تقسيم لوموتو يأخذ [[تعقيد الوقت|الوقت من الدرجة الثانية]] لفرز مجموعة من القيم متساوية. ومع ذلك، باستخدام خوارزمية التقسيم مثل نظام تقسيم هور، تؤدي العناصر المتكررة عمومًا إلى تقسيم أفضل، وعلى الرغم من إمكانية حدوث مبادلات غير ضرورية للعناصر المساوية للمحور، فإن وقت التشغيل ينخفض بشكل عام مع زيادة عدد العناصر المتكررة (مع ذاكرة التخزين المؤقت تقليل حجم المبادلة). في حالة تساوي جميع العناصر، يقوم مخطط تقسيم هور بتبديل العناصر دون داع، ولكن التقسيم نفسه هو أفضل حالة، كما هو مذكور في قسم قسم هور أعلاه.

لحل مشكلة مخطط تقسيم لوموتو (تسمى أحيانًا [[مشكلة العلم الوطني الهولندي]] <ref name="engineering" />)، يمكن استخدام روتين بديل لتقسيم الوقت الخطي يفصل القيم إلى ثلاث مجموعات: القيم الأقل من المحور، والقيم التي تساوي المحور، والقيم الأكبر من المحور. (يسمي بنتلي وماكلروي هذا «قسمًا سمينًا» وقد تم تنفيذه بالفعل في{{مونو|[[دالة qsort]]}} من [[نظام يونكس السابع|الإصدار 7 يونكس]].<ref name="engineering" />) القيم التي تساوي المحور تم فرزها بالفعل، لذا يجب فرز الأقسام الأصغر من والأكبر من فقط بشكل متكرر. في الكود الزائف، تصبح خوارزمية الفرز السريع<syntaxhighlight lang="logtalk">
algorithm quicksort(A, lo, hi) is
  if lo < hi then
    p := pivot(A, lo, hi)
    left, right := partition(A, p, lo, 
hi) // note: multiple return values
    quicksort(A, lo, left - 1) 
    quicksort(A, right + 1, hi)
</syntaxhighlight>يقوم <code>partition</code> بإرجاع المؤشرات إلى العنصر الأول («أقصى اليسار») وإلى العنصر الأخير («أقصى اليمين») من القسم الأوسط. كل عنصر من القسم يساوي <code>p</code> وبالتالي يتم فرزها. وبالتالي، لا يلزم تضمين عناصر القسم في الاستدعاءات المتكررة <code>ترتيب سريع</code> .

تحدث أفضل حالة للخوارزمية الآن عندما تكون جميع العناصر متساوية (أو يتم اختيارها من مجموعة صغيرة من {{تعبير رياضي|''k'' ≪ ''n''}}). في حالة كل العناصر المتساوية، سينفذ التصنيف السريع المعدل مكالمتين متتاليتين فقط على المصفوفات الفرعية الفارغة، وبالتالي ينتهي في الوقت الخطي (بافتراض أن <code>partition</code> الفرعي لا يستغرق أكثر من الوقت الخطي).

==== التحسينات ====
هناك نوعان من التحسينات المهمة الأخرى، التي اقترحها سيدجويك والمستخدمة على نطاق واسع في الممارسة، هي:<ref name="glibc_qsort">qsort.c in [[مكتبة جنو لسي]]:,</ref>

* للتأكد من استخدام مساحة {{تعبير رياضي|''O''(log ''n'')}} [[wiktionary:recurse|على الأكثر، قم بالتكرار]] أولاً في الجانب الأصغر من القسم، ثم استخدم [[نداء الذيل|استدعاء الذيل]] للتكرار في الجانب الآخر، أو قم بتحديث المعلمات بحيث لا تتضمن بعد الآن الجانب الأصغر المصنف الآن، وكرر لفرز الجانب الأكبر.
* عندما يكون عدد العناصر أقل من بعض العتبة (ربما عشرة عناصر)، قم بالتبديل إلى خوارزمية فرز غير متكررة مثل [[ترتيب بالإدراج|فرز الإدراج]] الذي يؤدي إلى مقايضات أو مقارنات أو عمليات أخرى على مثل هذه المصفوفات الصغيرة. ستختلف «العتبة» المثالية بناءً على تفاصيل التنفيذ المحدد.
* متغير أقدم من التحسين السابق: عندما يكون عدد العناصر أقل من الحد {{Mvar|k}}، توقف ببساطة، ثم بعد معالجة المصفوفة بأكملها، قم بإجراء فرز للإدراج عليها. وقف الأوراق في وقت مبكر العودية -بترتيب {{Mvar|k}} بالمجموعة، وهذا يعني أن كل عنصر في معظم المناصب {{Mvar|k}} بعيدا عن موقفها النهائي فرزها. في هذه الحالة، يستغرق فرز {{تعبير رياضي|''O''(''kn'')}} لإنهاء الفرز، والذي يكون خطيًا إذا كان {{Mvar|k}} ثابتًا. {{استشهاد متعدد|sedgewickQsortPaper}} <ref name=":3" /> {{صفحات مرجع|117}} مقارنة بتحسين «العديد من الأنواع الصغيرة»، قد ينفذ هذا الإصدار تعليمات أقل، ولكنه يستخدم دون المستوى الأمثل [[ذاكرة مخبئية|لذاكرة التخزين المؤقت]] في أجهزة الكمبيوتر الحديثة.<ref name="LaMarca1999">{{استشهاد بدورية محكمة|الأول=Anthony|الأخير=LaMarca|الأول2=Richard E.|الأخير2=Ladner|عنوان=The Influence of Caches on the Performance of Sorting|صحيفة=Journal of Algorithms|المجلد=31|العدد=1|صفحات=66–104|DOI=10.1006/jagm.1998.0985|اقتباس=Although saving small subarrays until the end makes sense from an instruction count perspective, it is exactly the wrong thing to do from a cache performance perspective.|سنة=1999}}</ref>

==== التوازي ====
صيغة ترتيب سريع الخاصة بفرق تسد تجعلها قابلة [[خوارزمية متوازية|للتوازي]] باستخدام [[توازي المهام]]. يتم إنجاز خطوة التقسيم من خلال استخدام [[مجموع البادئة|خوارزمية مجموع البادئة المتوازية]] لحساب فهرس لكل عنصر مصفوفة في قسمها من المصفوفة المقسمة.<ref>Umut A. Acar, Guy E Blelloch, Margaret Reid-Miller, and Kanat Tangwongsan, [https://www.cs.cmu.edu/afs/cs/academic/class/15210-s13/www/lectures/lecture19.pdf Quicksort and Sorting Lower Bounds], ''Parallel and Sequential Data Structures and Algorithms''. 2013. {{Webarchive|url=https://web.archive.org/web/20170106102112/http://www.cs.cmu.edu/afs/cs/academic/class/15210-s13/www/lectures/lecture19.pdf |date=6 يناير 2017}}</ref><ref>{{استشهاد بدورية محكمة|عنوان=Quicksort Partition via Prefix Scan|سنة=2012|صحيفة=Dr. Dobb's|الأخير=Breshears|الأول=Clay|مسار= http://www.drdobbs.com/parallel/quicksort-partition-via-prefix-scan/240003109|مسار أرشيف= https://web.archive.org/web/20190725004426/http://www.drdobbs.com:80/parallel/quicksort-partition-via-prefix-scan/240003109
|تاريخ أرشيف=2019-07-25}}</ref> بالنظر إلى مجموعة من الحجم {{Mvar|n}}، تقوم خطوة التقسيم بتنفيذ {{تعبير رياضي|O(''n'')}} العمل في {{تعبير رياضي|''O''(log ''n'')}} الوقت وتتطلب {{تعبير رياضي|O(''n'')}} مساحة خدش إضافية. بعد تقسيم المصفوفة، يمكن فرز القسمين بشكل متكرر على التوازي. {{تعبير رياضي|O(log² ''n'')}} المتوازي يفرز مجموعة من الحجم {{Mvar|n}} في {{تعبير رياضي|O(''n'' log ''n'')}} تعمل في {{تعبير رياضي|O(log² ''n'')}} الوقت باستخدام {{تعبير رياضي|O(''n'')}} مساحة إضافية.

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

يمكن أن تحقق خوارزميات الفرز المتوازي الأخرى الأكثر تعقيدًا حدودًا زمنية أفضل.<ref>{{استشهاد بكتاب|الأول=Russ|مؤلف1=Miller|الأول2=Laurence|مؤلف2=Boxer|عنوان=Algorithms sequential & parallel: a unified approach|مسار= https://books.google.com/books?id=dZoZAQAAIAAJ|سنة=2000|ناشر=Prentice Hall|ISBN=978-0-13-086373-7|مسار أرشيف= https://web.archive.org/web/20170225004535/https://books.google.com/books?id=dZoZAQAAIAAJ
|تاريخ أرشيف=2017-02-25}}</ref> على سبيل المثال، في عام 1991، وصف ديفيد باورز [[آلة الوصول العشوائي المتوازية|الفرز السريع]] [[نوع الجذر|المتوازي (وفرز الجذر]] المرتبط) الذي يمكن أن يعمل في وقت {{تعبير رياضي|''O''(log ''n'')}} على القراءة المتزامنة والكتابة المتزامنة (CRCW) وآلة الوصول العشوائي المتوازية (PRAM) مع {{Mvar|n}} معالجات بواسطة أداء التقسيم ضمنيًا.<ref name="مولد تلقائيا1">{{استشهاد بمنشورات مؤتمر}}</ref>

== التحليل الرسمي ==

=== تحليل الحالة الأسوأ ===
يحدث القسم غير المتوازن عندما تكون إحدى القوائم الفرعية التي يتم إرجاعها بواسطة إجراء التقسيم بحجم {{تعبير رياضي|''n'' − 1}}.<ref name="unbalanced">The other one may either have {{تعبير رياضي|1}} element or be empty (have {{تعبير رياضي|0}} elements), depending on whether the pivot is included in one of subpartitions, as in the Hoare's partitioning routine, or is excluded from both of them, like in the Lomuto's routine.</ref> قد يحدث هذا إذا كان المحور هو أصغر أو أكبر عنصر في القائمة، أو في بعض عمليات التنفيذ (على سبيل المثال، نظام تقسيم لوموتو كما هو موضح أعلاه) عندما تكون جميع العناصر متساوية.

إذا حدث هذا بشكل متكرر في كل قسم، فإن كل مكالمة متكررة تعالج قائمة بحجم أقل من القائمة السابقة. وبالتالي، يمكننا إجراء {{تعبير رياضي|''n'' − 1}} قبل أن نصل إلى قائمة الحجم 1. هذا يعني أن [[مكدس المكالمات|شجرة الاستدعاء]] عبارة عن سلسلة خطية من المكالمات المتداخلة {{تعبير رياضي|''n'' − 1}} {{Mvar|i}} عشر دعوة يفعل {{تعبير رياضي|''O''(''n'' − ''i'')}} العمل للقيام به القسم، و <math>\textstyle\sum_{i=0}^n (n-i) = O(n^2)</math>، وذلك في هذه الحالة فرز سريع يأخذ {{تعبير رياضي|''O''(''n''²)}} وقت {{تعبير رياضي|''O''(''n''²)}}

=== تحليل أفضل حالة ===
في الحالة الأكثر توازناً، في كل مرة نقوم فيها بإجراء قسم، نقسم القائمة إلى قسمين متساويين تقريبًا. هذا يعني أن كل مكالمة متكررة تعالج قائمة من نصف الحجم. ونتيجة لذلك، يمكننا أن نجعل فقط {{تعبير رياضي|log<sub>2</sub> ''n''}} المتداخلة المكالمات قبل أن نصل إلى قائمة حجم 1. هذا يعني أن عمق [[مكدس المكالمات|شجرة الاستدعاء]] هو {{تعبير رياضي|log<sub>2</sub> ''n''}} . لكن لا يوجد مكالمتان على نفس المستوى من شجرة الاستدعاء تعالج نفس الجزء من القائمة الأصلية ؛ وبالتالي، فإن كل مستوى من المكالمات يحتاج فقط إلى وقت {{تعبير رياضي|''O''(''n'')}} معًا (كل مكالمة لها بعض الحمل الثابت، ولكن نظرًا لوجود {{تعبير رياضي|''O''(''n'')}} في كل مستوى، يتم تضمين ذلك في {{تعبير رياضي|''O''(''n'')}} عامل). والنتيجة هي أن الخوارزمية تستخدم الوقت {{تعبير رياضي|''O''(''n'' log ''n'')}} فقط.

=== تحليل متوسط الحالة ===
لفرز مجموعة من العناصر المتميزة {{Mvar|n}} {{تعبير رياضي|''O''(''n'' log ''n'')}} في التوقع، بمتوسط كل {{تعبير رياضي|''n''!}} تباديل عناصر {{Mvar|n}} [[توزيع منتظم متقطع|باحتمالية متساوية]]. نسرد هنا ثلاثة أدلة شائعة لهذا الادعاء تقدم رؤى مختلفة حول طريقة عمل الترتيب السريع.

==== باستخدام النسب المئوية ====
إذا كان لكل محور مرتبة في مكان ما في منتصف 50 بالمائة، أي بين 25 [[مئين (إحصاء)|بالمائة]] و 75 بالمائة، فإنه يقسم العناصر بنسبة 25٪ على الأقل و 75٪ على الأكثر على كل جانب. إذا تمكنا من اختيار هذه المحاور باستمرار، فسنضطر فقط إلى تقسيم القائمة على الأكثر <math>\log_{4/3} n</math> مرات قبل الوصول إلى قوائم الحجم 1، مما ينتج عنه خوارزمية {{تعبير رياضي|''O''(''n'' log ''n'')}}

عندما يكون الإدخال تبديلًا عشوائيًا، يكون للمحور ترتيب عشوائي، وبالتالي لا يمكن ضمان أن يكون في منتصف 50 بالمائة. ومع ذلك، عندما نبدأ من التقليب العشوائي، في كل استدعاء تكراري، يكون للمحور ترتيب عشوائي في قائمته، وبالتالي فهو في منتصف 50 بالمائة تقريبًا نصف الوقت. هذا جيد بما فيه الكفاية. تخيل أن عملة انقلبت: الرؤوس تعني أن رتبة المحور في منتصف 50 بالمائة، والذيل يعني أنه ليس كذلك. تخيل الآن أن العملة انقلبت مرارًا وتكرارًا حتى تحصل على شكل {{Mvar|k}} . على الرغم من أن هذا قد يستغرق وقتًا طويلاً، إلا أنه في المتوسط {{تعبير رياضي|2''k''}} فقط، واحتمال عدم حصول العملة المعدنية على رؤوس {{Mvar|k}} {{تعبير رياضي|100''k''}} أمر غير محتمل للغاية (يمكن جعل هذا صارمًا باستخدام [[ملزمة تشيرنوف|حدود تشيرنوف]]). من خلال نفس الوسيطة، سينتهي عودية ترتيب سريع في المتوسط عند عمق مكالمة فقط <math>2 \log_{4/3} n</math> . ولكن إذا كان متوسط عمق المكالمة هو {{تعبير رياضي|''O''(log ''n'')}}، وكل مستوى من عمليات شجرة الاستدعاء في معظم {{Mvar|n}} العناصر، فإن إجمالي مقدار العمل المنجز في المتوسط هو المنتج {{تعبير رياضي|''O''(''n'' log ''n'')}} . لا يتعين على الخوارزمية التحقق من أن المحور يقع في النصف الأوسط - إذا ضربناه بأي جزء ثابت من المرات، فهذا يكفي للتعقيد المطلوب.

==== باستخدام التكرارات ====
طريقة بديلة هي إنشاء [[علاقة استدعاء ذاتي|علاقة تكرار]] {{تعبير رياضي|''T''(''n'')}}، الوقت اللازم لفرز قائمة بالحجم {{Mvar|n}} . في أكثر الحالات غير المتوازنة، تتضمن مكالمة الفرز السريع الفردية {{تعبير رياضي|''O''(''n'')}} العمل بالإضافة إلى مكالمتين متكررتين على قوائم الحجم {{تعبير رياضي|0}} و {{تعبير رياضي|''n''−1}}، وبالتالي فإن علاقة التكرار هي

<math>T(n) = O(n) + T(0) + T(n-1) = O(n) + T(n-1).</math>

هذه هي نفس العلاقة بالنسبة [[ترتيب بالإدراج|لفرز الإدراج وفرز]] [[ترتيب انتقائي|التحديد]]، وهي تحل أسوأ حالة {{تعبير رياضي|''T''(''n'') {{=}} ''O''(''n''²)}} .

في الحالة الأكثر توازناً، تتضمن مكالمة الفرز السريع الفردية عمل {{تعبير رياضي|''O''(''n'')}} بالإضافة إلى مكالمتين متكررتين على قوائم بحجم {{تعبير رياضي|''n''/2}}، وبالتالي فإن علاقة التكرار هي

: <math>T(n) = O(n) + 2T\left(\frac{n}{2}\right).</math>
: تخبرنا [[النظرية الرئيسة (تحليل الخوارزميات)|النظرية الرئيسية لتكرار فرق تسد]] {{تعبير رياضي|''T''(''n'') {{=}} ''O''(''n'' log ''n'')}} .
: يتبع مخطط إثبات رسمي لتعقيد الوقت المتوقع {{تعبير رياضي|''O''(''n'' log ''n'')}} افترض أنه لا توجد نسخ مكررة حيث يمكن التعامل مع التكرارات بوقت خطي قبل المعالجة وبعدها، أو اعتبار الحالات أسهل من التي تم تحليلها. عندما يكون الإدخال عبارة عن تبديل عشوائي، فإن رتبة المحور تكون عشوائية منتظمة من 0 إلى {{تعبير رياضي|''n'' − 1}} . ثم يكون للأجزاء الناتجة من القسم أحجام {{Mvar|i}} و {{تعبير رياضي|''n'' − ''i'' − 1}}، وأنا عشوائي منتظم من 0 إلى {{تعبير رياضي|''n'' − 1}} . لذلك، عند حساب المتوسط على جميع الانقسامات الممكنة مع ملاحظة أن عدد المقارنات للقسم هو {{تعبير رياضي|''n'' − 1}}، يمكن تقدير متوسط عدد المقارنات عبر جميع تباديل تسلسل الإدخال بدقة عن طريق حل علاقة التكرار:
:: <math>C(n) = n - 1 + \frac{1}{n} \sum_{i=0}^{n-1} (C(i)+C(n-i-1)) = n - 1 + \frac{2}{n} \sum_{i=0}^{n-1} C(i)</math>
:: <math>n C(n) = n (n - 1) + 2 \sum_{i=0}^{n-1} C(i)</math>

: <math>n C(n) - (n - 1) C(n - 1) = n (n - 1) - (n - 1) (n - 2) + 2 C(n - 1)</math>

: <math>n C(n) = (n + 1) C(n - 1) + 2n - 2</math>
:: <math>\begin{align}
\frac{C(n)}{n + 1} & = \frac{C(n - 1)}{n} + \frac{2}{n+1} - \frac{2}{n(n+1)} \le \frac{C(n - 1)}{n} + \frac{2}{n+1} \\
& = \frac{C(n-2)}{n-1} + \frac{2}{n} - \frac{2}{(n-1)n} + \frac{2}{n+1} \le \frac{C(n-2)}{n-1} + \frac{2}{n} + \frac{2}{n+1} \\
& \ \ \vdots \\
& = \frac{C(1)}{2} + \sum_{i=2}^n \frac{2}{i + 1}
\leq 2 \sum_{i=1}^{n-1} \frac{1}{i} 
\approx 2 \int_1^n \frac{1}{x} \mathrm{d} x = 2 \ln n
\end{align}
</math>
: يعطي حل التكرار {{تعبير رياضي|''C''(''n'') {{=}} 2''n'' ln ''n'' ≈ 1.39''n'' log₂ ''n''}} .

هذا يعني أن الترتيب السريع، في المتوسط، يؤدي فقط نحو 39٪ أسوأ مما كان عليه في أفضل حالاته. وبهذا المعنى، فهي أقرب إلى الحالة الأفضل من الحالة الأسوأ. لا [[نوع المقارنة|يمكن لفرز المقارنة]] استخدام مقارنات أقل من {{تعبير رياضي|log₂(''n''!)}} في المتوسط لفرز {{Mvar|n}} العناصر (كما هو [[نوع المقارنة|موضح في مقالة فرز المقارنة]]) وفي حالة {{Mvar|n}} الكبيرة، ينتج عن [[تقريب ستيرلينغ]] {{تعبير رياضي|log₂(''n''!) ≈ ''n''(log₂ ''n'' − log₂ ''e'')}}، لذا فإن الترتيب السريع ليس أسوأ بكثير من نوع المقارنة المثالي. يعد متوسط وقت التشغيل السريع هذا سببًا آخر للهيمنة العملية للفرز السريع على خوارزميات الفرز الأخرى.

==== استخدام شجرة بحث ثنائية ====
[[شجرة بحث ثنائية|تتوافق شجرة البحث الثنائية]] التالية (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> .

إصلاح {{Mvar|i}} و {{تعبير رياضي|''j''<''i''}} . القيم <math>{x_1,x_2,\ldots,x_j}</math> بمجرد الفرز، حدد فترات {{تعبير رياضي|''j''+1}} الملاحظة الهيكلية الأساسية هي أن <math>x_i</math> بالمقارنة مع <math>x_j</math> في الخوارزمية إذا وفقط إذا <math>x_i</math> يقع داخل أحد الفترتين المتجاورتين لـ <math>x_j</math> .

لاحظ ذلك منذ ذلك الحين <math>(x_1,x_2,\ldots,x_n)</math> هو تبديل عشوائي، <math>(x_1,x_2,\ldots,x_j,x_i)</math> هو أيضًا تبديل عشوائي، لذا فإن الاحتمال <math>x_i</math> مجاور ل <math>x_j</math> هو بالضبط <math>\frac{2}{j+1}</math> .

ننتهي بحساب قصير:

<math>\operatorname{E}[C] = \sum_i \sum_{j<i} \frac{2}{j+1} = O\left(\sum_i \log i\right)=O(n \log n).</math>

=== تعقيد الفضاء ===
المساحة التي يستخدمها الترتيب السريع تعتمد على الإصدار المستخدم.
يحتوي الإصدار الموضعي من الترتيب السريع على تعقيد مساحة {{تعبير رياضي|''O''(log ''n'')}}، حتى في أسوأ الحالات، عندما يتم تنفيذه بعناية باستخدام الاستراتيجيات التالية:

* يتم استخدام التقسيم الموضعي. يتطلب هذا القسم غير المستقر مساحة {{تعبير رياضي|''O''(1)}}
* بعد التقسيم، يتم فرز القسم الذي يحتوي على أقل عدد من العناصر (بشكل متكرر) أولاً، مما يتطلب مساحة {{تعبير رياضي|''O''(log ''n'')}} ثم يتم فرز القسم الآخر باستخدام [[عودة الذيل|تكرار الذيل]] أو التكرار، والذي لا يضيف إلى مكدس الاستدعاءات. هذه الفكرة، كما تمت مناقشتها أعلاه، وصفها [[روبرت سيدجويك (عالم كمبيوتر)|روبرت سيدجويك]]، وتحافظ على عمق المكدس المحدد بـ {{تعبير رياضي|''O''(log ''n'')}}.<ref name="sedgewickBook2">{{استشهاد بكتاب|مؤلف1=Sedgewick|الأول=Robert|مؤلف-وصلة=Robert Sedgewick (computer scientist)|عنوان=Algorithms in C: Fundamentals, Data Structures, Sorting, Searching, Parts 1–4|مسار=https://books.google.com/books?id=ylAETlep0CwC|طبعة=3|تاريخ=1 September 1998|ناشر=Pearson Education|ISBN=978-81-317-1291-7| مسار أرشيف = https://web.archive.org/web/20200820030743/https://books.google.com/books?id=ylAETlep0CwC | تاريخ أرشيف = 20 أغسطس 2020 }}</ref><ref name="sedgewickQsortPaper">{{استشهاد بدورية محكمة|الأخير=Sedgewick|الأول=R.|عنوان=Implementing Quicksort programs|DOI=10.1145/359619.359631|صحيفة={{Ill-WD2|Comm. ACM|id=Q1120519}}|المجلد=21|العدد=10|صفحات=847–857|سنة=1978}}</ref>

ترتيب سريع مع التقسيم الموضعي وغير المستقر يستخدم مساحة إضافية ثابتة فقط قبل إجراء أي مكالمة متكررة. يجب أن يقوم ترتيب سريع بتخزين قدر ثابت من المعلومات لكل مكالمة متكررة متداخلة. نظرًا لأن أفضل حالة تجعل على الأكثر استدعاءات متكررة متداخلة {{تعبير رياضي|''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'')}} لتخزين العمل ويمكنه تنفيذ فرز مستقر. تسمح مساحة التخزين العاملة بتقسيم مصفوفة الإدخال بسهولة بطريقة مستقرة ثم نسخها مرة أخرى إلى مصفوفة الإدخال لإجراء مكالمات متكررة متتالية. لا يزال تحسين روبرت سيدجويك مناسبًا.

== ملخص خطوات الخوارزمية ==
* أولا : نقوم باختيار '''المحور أو الأساس'''
* ثانيا : نقوم بإنشاء ثلاث مصفوفات واحد G تحتوي على العناصر التي هي أكبر من المحور، الثانية E وهي تحتوي على عناصر التي هي مساوية
للمحور، الثالثة وهي L وهي تحتوي على العناصر التي هي اقل من المحور
* ثالثا : نقوم بعمل استدعاء ذاتي على المصفوفة L، G
* رابعا : عند الوصول إلى مرحلة تكون فيها عدد العناصر في المصوفة اقل من 2 أي واحد تكون عناصر مصفوفة مرتبة لانها تحتوي على عنصر
واحد فقط !
* خامسا: نقوم بخطوة التجميع وهي تتصمن جمع المصوفات الثلاث في مصفوفة جديدة بترتيب حيث نضع المصفوفة L ثم E ثم G فيصبح لدينا مصموفة
تحتوي على العناصر مرتبة

=== مثال ===
<div style="direction:ltr;">
 '''algorithm''' ترتيب سريع (A, lo, hi) '''is'''
 '''if''' lo < hi '''then'''
 pp:= partition(A, lo, hi)
 ترتيب سريع (A, lo, p – 1)
 ترتيب سريع (A, p + 1, hi)

 '''algorithm''' partition(A, lo, hi) '''is'''
 pivot := A[hi]
 i := lo ''// place for swapping''
 '''for''' j := lo '''to''' hi – 1 '''do'''
 '''if''' A[j] ≤ pivot '''then'''
 swap A[i] with A[j] 
 i := i + 1
 swap A[i] with A[hi]
 '''return''' i
</div>

يتم ترتيب المصفوفة باستدعاء {{يسار إلى يمين|quicksort(A, 1, length(A))}}.

== العلاقة بالخوارزميات الأخرى ==
ترتيب سريع هو نسخة محسّنة للمساحة [[نوع الشجرة الثنائية|لفرز الشجرة الثنائية]]. بدلاً من إدراج العناصر بشكل تسلسلي في شجرة صريحة، يقوم التصنيف السريع بتنظيمها بشكل متزامن في شجرة تتضمنها المكالمات المتكررة. تقوم الخوارزميات بإجراء نفس المقارنات تمامًا، ولكن بترتيب مختلف. من الخصائص المرغوبة غالبًا [[خوارزمية ترتيب|لخوارزمية الفرز]] الاستقرار - حيث لا يتم تغيير ترتيب العناصر التي تقارن التساوي، مما يسمح بالتحكم في ترتيب جداول مالتيكاي (مثل قوائم الدليل أو المجلدات) بطريقة طبيعية. هذه المنشأة السياحية من الصعب الحفاظ عليها في الموقع فرز سريع (أو في مكان) (أي استخدامات فقط مساحة إضافية المستمر لمؤشرات ومخازن، {{تعبير رياضي|''O''(log ''n'')}} مساحة إضافية لإدارة العودية الصريحة أو الضمنية). بالنسبة للفرز السريع المتغير الذي يتضمن ذاكرة إضافية بسبب التمثيلات باستخدام المؤشرات (مثل القوائم أو الأشجار) أو الملفات (القوائم الفعالة)، فمن التافه الحفاظ على الاستقرار. تميل هياكل البيانات الأكثر تعقيدًا أو المرتبطة بالقرص إلى زيادة تكلفة الوقت، مما يؤدي بشكل عام إلى زيادة استخدام الذاكرة الافتراضية أو القرص.

المنافس المباشر [[تصنيف الكومة|للفرز السريع]] هو كومة. وقت تشغيل هيبسورت هو {{تعبير رياضي|''O''(''n'' log ''n'')}}، لكن متوسط وقت تشغيل هيبسورت يُعتبر عادةً أبطأ من الترتيب السريع في المكان.<ref name="مولد تلقائيا1" /> هذه النتيجة قابلة للنقاش. تشير بعض المنشورات إلى عكس ذلك.<ref>{{استشهاد بويب
| مسار = http://www.azillionmonkeys.com/qed/sort.html
| عنوان = Sorting revisited
| سنة = 2004
| ناشر = azillionmonkeys.com
| الأخير = Hsieh
| الأول = Paul
| مسار أرشيف = https://web.archive.org/web/20210107174056/http://www.azillionmonkeys.com/qed/sort.html | تاريخ أرشيف = 7 يناير 2021 }}</ref><ref>{{استشهاد بويب
| مسار = http://www.inference.org.uk/mackay/sorting/sorting.html
| عنوان = Heapsort, Quicksort, and Entropy
| تاريخ = December 2005
| مسار أرشيف = https://web.archive.org/web/20090401163041/http://users.aims.ac.za/~mackay/sorting/sorting.html
| تاريخ أرشيف = 1 April 2009
| الأخير = MacKay
| الأول = David
}}</ref> [[مقدمة (توضيح)|إنتروسورت هو أحد أنواع الفرز السريع]] الذي يتحول إلى الترتيب المتراكم عند اكتشاف حالة سيئة لتجنب وقت تشغيل الترتيب السريع في أسوأ الحالات.

يتنافس ترتيب سريع أيضًا مع [[تصنيف دمجي|فرز الدمج]]، وهو خوارزمية فرز {{تعبير رياضي|''O''(''n'' log ''n'')}} يعد ميرجسورت [[خوارزمية ترتيب|نوعًا مستقرًا]]، على عكس الترتيب السريع في المكان القياسي والفرز المتراكم، ويتميز بأداء ممتاز في أسوأ الحالات. العيب الرئيسي لفرز الدمج هو أنه عند التشغيل على المصفوفات، تتطلب التطبيقات الفعالة {{تعبير رياضي|''O''(''n'')}}، في حين أن متغير الفرز السريع مع التقسيم الموضعي والتكرار الخلفي يستخدم مساحة {{تعبير رياضي|''O''(log ''n'')}}

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

[[فرز دلو|يشبه الفرز دلو]] مع دلاء إلى حد كبير الفرز السريع ؛ المحور في هذه الحالة هو بشكل فعال القيمة الموجودة في منتصف نطاق القيمة، والتي تعمل بشكل جيد في المتوسط للمدخلات الموزعة بشكل موحد.

=== التمحور القائم على الاختيار ===
A [[خوارزمية الاختيار|اختيار خوارزمية]] يختار {{Mvar|k}} أصغر من قائمة بأرقام عشر. هذه مشكلة أسهل بشكل عام من الفرز. تعمل خوارزمية اختيار بسيطة ولكنها فعالة بنفس طريقة الترتيب السريع تقريبًا، وبالتالي تُعرف باسم [[حدد مسرعا|التحديد السريع]]. الفرق هو أنه بدلاً من إجراء مكالمات متكررة على كلتا القائمتين الفرعيتين، فإنه يقوم فقط بإجراء مكالمة متكررة ذيل واحدة في القائمة الفرعية التي تحتوي على العنصر المطلوب. يقلل هذا التغيير من متوسط التعقيد إلى الوقت الخطي أو {{تعبير رياضي|''O''(''n'')}}، وهو الأمثل للاختيار، لكن خوارزمية الفرز لا تزال {{تعبير رياضي|''O''(''n''<sup>2</sup>)}} .

يختار أحد متغيرات التحديد السريع، وهو [[متوسط المتوسطات|متوسط]] خوارزمية المتوسطات، المحاور بدقة أكبر، مما يضمن أن المحاور قريبة من منتصف البيانات (بين النسب المئوية 30 و 70)، وبالتالي تضمن الوقت الخطي - {{تعبير رياضي|''O''(''n'')}} . يمكن استخدام نفس إستراتيجية المحور هذه لإنشاء متغير من الترتيب السريع (متوسط الفرز السريع للوسيطات {{تعبير رياضي|''O''(''n'' log ''n'')}} بوقت {{تعبير رياضي|''O''(''n'' log ''n'')}} ومع ذلك، فإن النفقات العامة لاختيار المحور مهمة، لذلك لا يتم استخدام هذا بشكل عام في الممارسة.

بشكل أكثر تجريدًا، بالنظر إلى {{تعبير رياضي|''O''(''n'')}}، يمكن للمرء استخدامها للعثور على المحور المثالي (الوسيط) في كل خطوة من الترتيب السريع، وبالتالي إنتاج خوارزمية فرز مع وقت تشغيل {{تعبير رياضي|''O''(''n'' log ''n'')}} تكون التطبيقات العملية لهذا المتغير أبطأ إلى حد كبير في المتوسط، لكنها ذات أهمية نظرية لأنها تظهر أن خوارزمية اختيار مثالية يمكن أن تسفر عن خوارزمية فرز مثالية.

=== المتغيرات ===

==== الترتيب السريع متعدد المحاور ====
بدلا من تقسيم إلى قسمين المصفوفات الفرعية باستخدام محور واحد، فرز سريع متعدد محور (أيضا متعدد ترتيب سريع {{استشهاد متعدد|LaMarca1999}}) تقسيم مدخلاته إلى بعض رقم {{Mvar|s}} من المصفوفات الفرعية باستخدام {{تعبير رياضي|''s'' − 1}} المحاور. في حين تم النظر في حالة المحور المزدوج ({{تعبير رياضي|''s'' {{=}} 3}}) بواسطة سيدجويك وآخرون بالفعل في منتصف السبعينيات، لم تكن الخوارزميات الناتجة أسرع في الممارسة العملية من الترتيب السريع «الكلاسيكي».<ref name="مولد تلقائيا1" /> وجد تقييم عام 1999 لـ متعدد ترتيب سريع مع عدد متغير من المحاور، تم ضبطها لتحقيق الاستخدام الفعال لذاكرة التخزين المؤقت للمعالج، أنها تزيد من عدد التعليمات بحوالي 20٪، لكن نتائج المحاكاة تشير إلى أنها ستكون أكثر كفاءة مع المدخلات الكبيرة جدًا. {{استشهاد متعدد|LaMarca1999}} هناك نسخة من التصنيف السريع ثنائي المحور طوره ياروسلافسكي في عام 2009 <ref name=":0" /> تبين أنها سريعة بما يكفي لضمان التنفيذ في [[سجل إصدار جافا|جافا 7]]، حيث أن الخوارزمية القياسية لفرز مصفوفات العناصر [[أنواع البيانات الأولية|الأولية]] (يتم فرز مصفوفات [[كائن (حوسبة)|الكائنات]] باستخدام [[تيمسورت|تايمسورت]]).<ref>{{استشهاد بويب
| مسار = http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort%28byte%5B%5D%29
| عنوان = Arrays
| موقع = Java Platform SE 7
| ناشر = Oracle
| تاريخ الوصول = 4 September 2014
| مسار أرشيف = https://web.archive.org/web/20201112040249/https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(byte[]) | تاريخ أرشيف = 12 نوفمبر 2020 }}</ref> تم العثور لاحقًا على أن فائدة أداء هذه الخوارزمية مرتبطة في الغالب بأداء ذاكرة التخزين المؤقت، <ref>{{استشهاد بأرخايف|عنوان=Why Is Dual-Pivot Quicksort Fast?|الأخير=Wild}}</ref> وتشير النتائج التجريبية إلى أن المتغير ثلاثي المحاور قد يؤدي بشكل أفضل على الأجهزة الحديثة.<ref name="مولد تلقائيا1" /><ref name="مولد تلقائيا1" />

==== فرز سريع خارجي ====
بالنسبة لملفات القرص، من الممكن إجراء فرز خارجي يعتمد على تقسيم مشابه للترتيب السريع. إنه أبطأ من فرز الدمج الخارجي، لكنه لا يتطلب مساحة قرص إضافية. يتم استخدام 4 مخازن، 2 للإدخال، 2 للإخراج. دع N = عدد السجلات في الملف، B = عدد السجلات لكل مخزن مؤقت، و M = N / B = عدد مقاطع المخزن المؤقت في الملف. تتم قراءة البيانات (وكتابتها) من طرفي الملف إلى الداخل. دع X تمثل المقاطع التي تبدأ في بداية الملف وتمثل Y المقاطع التي تبدأ في نهاية الملف. تتم قراءة البيانات في المخازن المؤقتة للقراءة X و Y. يتم اختيار سجل محوري ويتم نسخ السجلات الموجودة في المخازن المؤقتة X و Y بخلاف السجل المحوري إلى المخزن المؤقت للكتابة X بترتيب تصاعدي والمخزن المؤقت للكتابة Y بترتيب تنازلي على أساس المقارنة مع السجل المحوري. بمجرد ملء المخزن المؤقت X أو Y، تتم كتابته في الملف ويتم قراءة المخزن المؤقت X أو Y التالي من الملف. تستمر العملية حتى تتم قراءة جميع المقاطع ويبقى مخزن مؤقت واحد للكتابة. إذا كان هذا المخزن المؤقت عبارة عن مخزن مؤقت للكتابة على شكل X، فسيتم إلحاق السجل المحوري به وكتابة المخزن المؤقت X. إذا كان هذا المخزن المؤقت عبارة عن مخزن مؤقت للكتابة على شكل Y، يتم إرسال السجل المحوري مسبقًا إلى المخزن المؤقت Y ويتم كتابة المخزن المؤقت Y. يشكل هذا خطوة قسم واحدة للملف، ويتكون الملف الآن من ملفين فرعيين. يتم دفع / ظهور مواضع البداية والنهاية لكل ملف فرعي إلى مكدس مستقل أو المكدس الرئيسي عبر العودية. لتقييد مساحة المكدس بـ O (log2 (n))، تتم معالجة الملف الفرعي الأصغر أولاً. بالنسبة للمكدس المستقل، ادفع معلمات الملف الفرعي الأكبر إلى المكدس، ثم كرر على الملف الفرعي الأصغر. للتكرار، كرر على الملف الفرعي الأصغر أولاً، ثم كرر للتعامل مع الملف الفرعي الأكبر. بمجرد أن يكون الملف الفرعي أقل من أو يساوي 4 سجلات B، يتم فرز الملف الفرعي في مكانه عبر الترتيب السريع وكتابته. يتم الآن فرز هذا الملف الفرعي ووضعه في مكانه في الملف. تستمر العملية حتى يتم فرز جميع الملفات الفرعية ووضعها في مكانها الصحيح. متوسط عدد التمريرات على الملف هو تقريبًا 1 + ln (N + 1) / (4 B)، لكن نمط الحالة الأسوأ هو N عبر (ما يعادل O (n ^ 2) لأسوأ حالة فرز داخلي).<ref>[https://fdocuments.net/reader/full/an-efficient-external-sorting-with-minimal-space-requirement An efficient external sorting with minimal space requirement - [PDF Document&#93;<!-- عنوان مولد بالبوت -->] {{Webarchive|url=https://web.archive.org/web/20200621094253/https://fdocuments.net/reader/full/an-efficient-external-sorting-with-minimal-space-requirement |date=21 يونيو 2020}}</ref>

==== ثلاث طرق فرز سريع للجذر ====
هذه الخوارزمية عبارة عن مزيج من [[نوع الجذر|الفرز الأساسي]] والترتيب السريع. اختر عنصرًا من المصفوفة (المحور) واعتبر الحرف الأول (المفتاح) من السلسلة (مالتيكاي). قسّم العناصر المتبقية إلى ثلاث مجموعات: تلك التي يكون حرفها المقابل أقل من، ويساوي، وأكبر من حرف المحور. قم بفرز الأقسام «أصغر من» و «أكبر من» بشكل متكرر على نفس الحرف. قم بفرز قسم «يساوي» بشكل متكرر حسب الحرف التالي (مفتاح). بالنظر إلى أننا نقوم بالفرز باستخدام البايتات أو الكلمات ذات الطول {{Mvar|W}}، فإن أفضل حالة هي {{تعبير رياضي|''O''(''KN'')}} وأسوأ حالة {{تعبير رياضي|''O''(2<sup>''K''</sup>''N'')}} أو على الأقل {{تعبير رياضي|''O''(''N''<sup>2</sup>)}} كما هو الحال بالنسبة للترتيب السريع القياسي، المعطى للمفاتيح الفريدة {{تعبير رياضي|''N''<2<sup>''K''</sup>}} و {{Mvar|K}} هو ثابت مخفي في جميع [[نوع المقارنة|خوارزميات فرز المقارنة]] القياسية بما في ذلك الفرز السريع. هذا نوع من الترتيب السريع ثلاثي الاتجاهات حيث يمثل القسم الأوسط مصفوفة فرعية مرتبة (تافهة) من العناصر التي ''تساوي تمامًا'' المحور.

==== فرز الجذر السريع ====
تم تطويره أيضًا بواسطة باورز باعتباره خوارزمية [[آلة الوصول العشوائي المتوازية]] {{تعبير رياضي|''O''(''K'')}} هذا مرة أخرى عبارة عن مزيج من [[نوع الجذر|فرز الجذر والفرز]] السريع ولكن يتم اتخاذ قرار التقسيم السريع الفرز الأيسر / الأيمن على بتات متتالية من المفتاح، وبالتالي يكون {{تعبير رياضي|''O''(''KN'')}} {{Mvar|N}} {{Mvar|K}} -bit. تفترض جميع [[نوع المقارنة|خوارزميات فرز المقارنة]] [[نموذج عبر التفرع|ضمنيًا النموذج متعدد التفرع]] مع {{Mvar|K}} في {{تعبير رياضي|''Θ''(log ''N'')}}، كما لو كانت {{Mvar|K}} أصغر، يمكننا الفرز في وقت {{تعبير رياضي|''O''(''N'')}} باستخدام جدول التجزئة أو [[فرز عدد صحيح]]. إذا كانت {{تعبير رياضي|''K'' ≫ log ''N''}} ولكن العناصر فريدة داخل {{تعبير رياضي|''O''(log ''N'')}}، فلن يتم النظر إلى البتات المتبقية من خلال الفرز السريع أو الفرز الأساسي السريع. إذا تعذر ذلك، فإن جميع خوارزميات فرز المقارنة سيكون لها أيضًا نفس النفقات العامة للبحث من خلال {{تعبير رياضي|''O''(''K'')}} بتات عديمة الفائدة نسبيًا ولكن الفرز السريع للجذر سيتجنب أسوأ {{تعبير رياضي|''O''(''N''<sup>2</sup>)}} الخاصة بالفرز السريع القياسي والفرز السريع، وسيكون أسرع في أفضل حالة من خوارزميات المقارنة هذه في ظل ظروف {{تعبير رياضي|uniqueprefix(''K'') ≫ log ''N''}} راجع السلطات <ref>David M. W. Powers, [http://david.wardpowers.info/Research/AI/papers/199501-ACAW-PUPC.pdf Parallel Unification: Practical Complexity], Australasian Computer Architecture Workshop, Flinders University, January 1995 {{Webarchive|url=https://web.archive.org/web/20210203121318/http://david.wardpowers.info/Research/AI/papers/199501-ACAW-PUPC.pdf|date=2021-02-03}}</ref> لمزيد من المناقشة حول النفقات العامة المخفية في المقارنة، والجذر والفرز المتوازي.

==== كتلة الترتيب السريع ====
في أي خوارزمية فرز قائمة على المقارنة، يتطلب تقليل عدد المقارنات تعظيم كمية المعلومات المكتسبة من كل مقارنة، مما يعني أن نتائج المقارنة غير متوقعة. يتسبب هذا في [[متنبئ فروع|أخطاء]] متكررة في الفروع، مما يحد من الأداء.<ref name="مولد تلقائيا1" /> يقوم كتلة الترتيب السريع <ref>{{استشهاد بأرخايف|عنوان=BlockQuicksort: How Branch Mispredictions don't affect Quicksort|الأخير=Edelkamp}}</ref> بإعادة ترتيب حسابات التصنيف السريع لتحويل الفروع غير المتوقعة إلى [[تبعيات البيانات]]. عند التقسيم، يتم تقسيم الإدخال إلى [[حلقة منع|كتل]] متوسطة الحجم (تتناسب بسهولة مع [[ذاكرة مخبئية|ذاكرة التخزين المؤقت للبيانات]])، ويتم ملء صفيفين بمواضع العناصر المراد تبديلها. (لتجنب الفروع الشرطية، يتم تخزين الموضع دون قيد أو شرط في نهاية المصفوفة، ويزداد فهرس النهاية إذا كانت هناك حاجة إلى مبادلة.) يقوم التمرير الثاني بتبادل العناصر في المواضع المحددة في المصفوفات. تحتوي كلتا الحلقتين على فرع شرطي واحد فقط، وهو اختبار للإنهاء يتم إجراؤه عادةً.

==== فرز سريع جزئي وتزايدي ====
توجد العديد من المتغيرات من الترتيب السريع التي تفصل العناصر الأصغر أو الأكبر {{Mvar|k}}

=== تعميم ===
[[ريتشارد جيه كول|اكتشف ريتشارد جيه كول]] وديفيد سي. قندثيل، في عام 2004، عائلة مكونة من معلمة واحدة من خوارزميات الفرز، تسمى أنواع الأقسام، والتي تعمل في المتوسط (مع احتمالية متساوية لجميع أوامر الإدخال) على الأكثر <math>n\log n + {O}(n)</math> مقارنات (قريبة من الحد الأدنى النظري للمعلومات) و <math>{\Theta}(n\log n)</math> عمليات؛ في أسوأ الأحوال يؤدونها <math>{\Theta}(n\log^2 n)</math> المقارنات (وكذلك العمليات)؛ هذه في مكانها، وتتطلب إضافية فقط <math>{O}(\log n)</math> الفراغ. تم إثبات الكفاءة العملية والتباين الأصغر في الأداء مقابل الأنواع السريعة المحسّنة (لسيارات [[روبرت سيدجويك (عالم كمبيوتر)|سيدجويك]] و[[جون بنتلي (عالم حاسوب)|جون بنتلي]] - [[دوغلاس ماكلروي]]).<ref>Richard Cole, David C. Kandathil: [http://www.cs.nyu.edu/cole/papers/part-sort.pdf "The average case analysis of Partition sorts"], European Symposium on Algorithms, 14–17 September 2004, Bergen, Norway. Published: ''Lecture Notes in Computer Science'' 3221, Springer Verlag, pp. 240–251. {{Webarchive|url=https://web.archive.org/web/20191211132538/https://cs.nyu.edu/cole/papers/part-sort.pdf |date=11 ديسمبر 2019}}</ref>

== مراجع ==
{{مراجع}}

=== مصادر ===

* {{استشهاد بدورية محكمة|الأخير=Sedgewick|الأول=R.|عنوان=Implementing Quicksort programs|DOI=10.1145/359619.359631|صحيفة={{Ill-WD2|Comm. ACM|id=Q1120519}}|المجلد=21|العدد=10|صفحات=847–857|سنة=1978}}
* {{استشهاد بدورية محكمة|الأخير=Dean|الأول=B. C.|DOI=10.1016/j.dam.2005.07.005|عنوان=A simple expected running time analysis for randomized 'divide and conquer' algorithms|وصلة=https://archive.org/details/sim_discrete-applied-mathematics_2006-01-01_154_1/page/n12|صحيفة=Discrete Applied Mathematics|المجلد=154|صفحات=1–5|سنة=2006}}
* {{استشهاد بدورية محكمة|الأخير=Hoare|عنوان=Algorithm 63: Partition|DOI=10.1145/366622.366642|الأول=C. A. R.|صحيفة={{Ill-WD2|Comm. ACM|id=Q1120519}}|المجلد=4|العدد=7|صفحات=321|سنة=1961}}
* {{استشهاد بدورية محكمة|الأخير=Hoare|عنوان=Algorithm 65: Find|DOI=10.1145/366622.366647|الأول=C. A. R.|صحيفة={{Ill-WD2|Comm. ACM|id=Q1120519}}|المجلد=4|العدد=7|صفحات=321–322|سنة=1961}}
* {{استشهاد بدورية محكمة|الأخير=Hoare|الأول=C. A. R.|DOI=10.1093/comjnl/5.1.10|عنوان=Quicksort|صحيفة=[[مجلة الحاسوب]]|المجلد=5|العدد=1|صفحات=10–16|سنة=1962}} (أعيد طبعه في هور and Jones: [http://portal.acm.org/citation.cfm?id=SERIES11430.63445 ''Essays in Computing Science'']، 1989.)
* {{استشهاد بدورية محكمة|الأخير=Musser|الأول=David R.|مؤلف-وصلة=David Musser|عنوان=Introspective Sorting and Selection Algorithms|مسار= http://www.cs.rpi.edu/~musser/gp/introsort.ps|DOI=10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#|صحيفة=Software: Practice and Experience|المجلد=27|العدد=8|صفحات=983–993|سنة=1997|مسار أرشيف= https://web.archive.org/web/20210211081114/http://www.cs.rpi.edu/~musser/gp/introsort.ps
|تاريخ أرشيف=2021-02-11}}
* [[دونالد كينوث|دونالد كنوث]]. ''فن برمجة الكمبيوتر''، المجلد 3: ''الفرز والبحث''، الطبعة الثالثة. أديسون ويسلي، 1997.{{ردمك|0-201-89685-0}}[[النظام القياسي الدولي لترقيم الكتب|رقم ISBN]] [[خاص:BookSources/0-201-89685-0|0-201-89685-0]] . الصفحات 113-122 من القسم 5.2.2: الفرز عن طريق التبادل.
* [[توماس هـ.كورمين|توماس إتش كورمين]]، [[تشارلز إي ليسرسون|تشارلز إي ليسيرسون]]، [[رونالد ريفست|رونالد إل ريفيست]]، [[كليفورد شتاين|وكليفورد شتاين]]. ''[[مقدمة في الخوارزميات (كتاب)|مقدمة في الخوارزميات]]''، الطبعة الثانية. [[الصحافة MIT|مطبعة معهد ماساتشوستس للتكنولوجيا]] [[ماكجرو هيل التعليم|ومكجرو هيل]]، 2001.{{ردمك|0-262-03293-7}}[[النظام القياسي الدولي لترقيم الكتب|رقم ISBN]] [[خاص:BookSources/0-262-03293-7|0-262-03293-7]] . الفصل 7: ترتيب سريع، ص.&nbsp;145–164.
* [[فارون مولر]]. [http://www.cs.swan.ac.uk/~csfm/Courses/CS_332/quicksort.pdf تحليل ترتيب سريع] {{webarchive|url=https://web.archive.org/web/20070930231746/http://www.cs.swan.ac.uk/~csfm/Courses/CS_332/quicksort.pdf |date=30 سبتمبر 2007 }} . CS 332: تصميم الخوارزميات. قسم علوم الحاسوب، [[جامعة سوانسي]].
* {{استشهاد بدورية محكمة|الأخير=Martínez|الأول=C.|الأخير2=Roura|الأول2=S.|DOI=10.1137/S0097539700382108|عنوان=Optimal Sampling Strategies in Quicksort and Quickselect|صحيفة={{Ill-WD2|SIAM J. Comput.|id=Q7390263}}|المجلد=31|العدد=3|صفحات=683–705|سنة=2001}}
* {{استشهاد بدورية محكمة|الأخير=Bentley|الأول=J. L.|الأخير2=McIlroy|الأول2=M. D.|DOI=10.1002/spe.4380231105|عنوان=Engineering a sort function|مسار=https://archive.org/details/sim_software-practice-experience_1993-11_23_11/page/1249|صحيفة=Software: Practice and Experience|المجلد=23|العدد=11|صفحات=1249–1265|سنة=1993}}

== روابط خارجية ==

* {{استشهاد بويب
| مسار = http://www.sorting-algorithms.com/quick-sort
| عنوان = Animated Sorting Algorithms: Quick Sort
| مسار أرشيف = https://web.archive.org/web/20150302145415/http://www.sorting-algorithms.com/quick-sort
| تاريخ أرشيف = 2 March 2015
| تاريخ الوصول = 25 November 2008
}} - عرض رسومي
* {{استشهاد بويب
| مسار = http://www.sorting-algorithms.com/quick-sort-3-way
| عنوان = Animated Sorting Algorithms: Quick Sort (3-way partition)
| مسار أرشيف = https://web.archive.org/web/20150306071949/http://www.sorting-algorithms.com/quick-sort-3-way
| تاريخ أرشيف = 6 March 2015
| تاريخ الوصول = 25 November 2008
}}
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/11_1_Comparison_Based_Sorti.html#SECTION001412000000000000000 Open Data Structures - القسم 11.1.2 - ترتيب سريع]، [[بات مورين]]
* [https://web.archive.org/web/20180629183103/http://www.tomgsmith.com/quicksort/content/illustration/ رسم توضيحي تفاعلي لـ ترتيب سريع]، مع تجول التعليمات البرمجية
{{خوارزميات الترتيب}}
{{روابط شقيقة}}
{{شريط بوابات|برمجة الحاسوب|تقانة المعلومات|خوارزميات|رياضيات|عقد 1960|علم الحاسوب}}

[[تصنيف:علم الحاسوب في 1961]]
[[تصنيف:خوارزميات]]
[[تصنيف:خوارزميات الاختيار]]
[[تصنيف:خوارزميات البحث الثنائي]]
[[تصنيف:خوارزميات إحصائية]]
[[تصنيف:خوارزميات إدارة الذاكرة]]
[[تصنيف:خوارزميات إيجاد الجذور]]
[[تصنيف:خوارزميات بحث]]
[[تصنيف:خوارزميات تدقيق المجموع]]
[[تصنيف:خوارزميات ترتيب]]
[[تصنيف:خوارزميات π]]
[[تصنيف:مقالات تحوي أمثلة مكتوبة بشيفرة تقريبية]]