عرض مصدر الترتيب بالمقارنة

{{لا صندوق معلومات}}
{{ترجمة آلية}}

{{يتيمة|تاريخ=نوفمبر 2022}}

[[ملف:Balance_à_tabac_1850.JPG|يسار|تصغير| إن ترتيب مجموعة من الأوزان - غير محددة الوزن سابقا - باستخدام مقياس توازن فقط يتطلب خوارزمية ترتيب مبنية على المقارنات.]]
'''الترتيب بالمقارنة''' {{إنج|Comparison sort}} هو نوع من أنواع [[خوارزمية ترتيب|خوارزميات الترتيب]] التي تعتمد في عملها لترتيب عناصر قائمة ما على إجراء عملية مقارنة (غالبًا عملية «أقل من أو يساوي» أو مقارنة ثلاثية)، وتحدّد هذه المقارنة أي من العنصرين قيد المقارنة يجب أن يظهر أولاً في القائمة النهائية المرتبة. المتطلب الوحيد هو أن تقوم عملية المقارنة بعمل إعادة ترتيب للبيانات مع الأخذ بعين الاعتبار:

# إذا كانت ''a'' ≤ ''b'' وكانت ''b ≤'' ''c'' فإن ''a ≤'' ''c'' (علاقة التعدي)
# لكل من ''a'' و ''b''، فإن: ''a'' ≤ ''b أو b ≤ a'' (علاقة الإرتباط).

من الممكن أن يكون كلا ''من'' ''a'' ≤ ''b'' و ''b ≤ a'' صحيح؛ في هذه الحالة لا بد أن يكون العنصرين متساويين في القيمة، وقد يأتي أي منهما أولاً في القائمة المرتبة. في [[خوارزمية ترتيب|خوارزمية الترتيب المتّسمة بالثبات]]، يحدد ترتيب المدخلات ترتيب ظهور أي من العنصرين ''a أو b'' أولا في القائمة المرتبة.

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

== أمثلة ==
[[ملف:Sorting_quicksort_anim.gif|تصغير| [[ترتيب سريع|خوارزمية الترتيب السريع]] تعمل على ترتيب قائمة من الأرقام. الخطوط الأفقية هي القيم المحورية.]]
القائمة التالية تتضمن بعض أنواع المقارنة الأكثر شهرة:

* [[ترتيب سريع|الترتيب السريع]]
* [[تصنيف الكومة|ترتيب الكومة]]
* [[:en:Shellsort|ترتيب القذائف]]
* [[تصنيف دمجي|ترتيب الدمج]]
* [[:en:Introsort|ترتيب المقدمة]]
* [[ترتيب بالإدراج|ترتيب الإدراج]]
* [[ترتيب انتقائي|ترتيب الإختيار]]
* [[فرز فقاعي|ترتيب الفقاعة]]
* [[ترتيب الفردي الزوجي]]
* [[ترتيب كوكتيل شاكر]]
* [[ترتيب الدورة]]
* [[ترتيب الفرز والإدماج]]
* [[ترتيب سلس]]
* [[ترتيب تيم]]
* [[ترتيب الكتلة]]

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

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

قد تعمل بعض خوارزميات الترتيب بالمقارنة بشكل أسرع في بعض القوائم؛ تحتاج العديد من خوارزميات [[:en:Adaptive sort|الترتيب التكيفي]] مثل خوارزمية [[ترتيب بالإدراج|ترتيب الإدراج]] للتشغيل إلى O(''n'') من الوقت لترتيب مجموعة من العناصر في قائمة مرتبة بشكل كامل أو شبه مرتبة. وينطبق الحد الأدنى [[تمثيل O الكبرى|Ω]](''n'' log ''n'') فقط على الحالة التي تكون فيها عناصر القائمة بأي ترتيب عشوائي.

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

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

مثال على خوارزمية لإقتران مقارنة

 '''function''' tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc))
     '''if''' lefta ≠ righta
         '''return''' compare(lefta, righta)
     '''else if''' leftb ≠ rightb
         '''return''' compare(leftb, rightb)
     '''else'''
         '''return''' compare(leftc, rightc)

يسمح نظام العدّ [[الثلاثي المتوازن]] بإجراء مقارنات في خطوة واحدة فقط، تكون نتيجتها واحدة من ثلاث خيارات: «أقل من» أو «أكبر من» أو «يساوي».

خوارزميات الترتيب بالمقارنة تعمل عمومًا بسهولة مع أي نوع من أنواع المجموعات المعقدة مثل ترتيب [[:en:Floating-point arithmetic|الأعداد العشرية]]. بالإضافة إلى ذلك، بمجرد كتابة إقتران مقارنة، يمكن استخدام أي نوع من خوارزميات الترتيب بالمقارنة دون الحاجة للقيام بالتعديلات؛ فيما تتطلب عادة خوارزميات الترتيب التي لا تعتمد على المقارنات اقترانات ترتيب خاصة لكل نوع من البيانات. أدّت هذه المرونة في خوارزميات الترتيب بالمقارنة، بالإضافة إلى كفاءتها على أجهزة الحاسب الحديثة، إلى تفضيل واسع النطاق لخوارزميات الترتيب بالمقارنة في معظم الحلول العملية.

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

إن مشكلة [[فرز أزواج الأرقام]] غير خاضعة للحد الأدنى {{تعبير رياضي|Ω(''n''² log ''n'')}} (<small>التربيع في</small> ''n<sup>2</sup>'' <small>ناتج عن عملية بناء الأزواج</small>)؛ الخوارزمية الأكثر شيوعا تحتاج إلى وقت تشغيل {{تعبير رياضي|O(''n''² log ''n'')}}، فقط {{تعبير رياضي|O(''n''²)}} من المقارنات.

== عدد المقارنات المطلوبة لترتيب عناصر قائمة ==

{| class="wikitable" style="margin-right:auto; margin-right:auto;"
! ''n''
! <math>\left\lceil\log_2(n!)\right\rceil</math>
! الحد الأدنى
|-
| style="text-align:right;" | 1
| style="text-align:right;" | 0
| style="text-align:center;" | 0
|-
| style="text-align:right;" | 2
| style="text-align:right;" | 1
| style="text-align:center;" | 1
|-
| style="text-align:right;" | 3
| style="text-align:right;" | 3
| style="text-align:center;" | 3
|-
| style="text-align:right;" | 4
| style="text-align:right;" | 5
| style="text-align:center;" | 5
|-
| style="text-align:right;" | 5
| style="text-align:right;" | 7
| style="text-align:center;" | 7
|-
| style="text-align:right;" | 6
| style="text-align:right;" | 10
| style="text-align:center;" | 10
|-
| style="text-align:right;" | 7
| style="text-align:right;" | 13
| style="text-align:center;" | 13
|-
| style="text-align:right;" | 8
| style="text-align:right;" | 16
| style="text-align:center;" | 16
|-
| style="text-align:right;" | 9
| style="text-align:right;" | 19
| style="text-align:center;" | 19
|-
| style="text-align:right;" | 10
| style="text-align:right;" | 22
| style="text-align:center;" | 22
|-
| style="text-align:right;" | 11
| style="text-align:right;" | 26
| style="text-align:center;" | 26
|-
| style="text-align:right;" | 12
| style="text-align:right;" | 29
| style="text-align:center;" | 30 <ref name="Wells1965">Mark Wells, Applications of a language for computing in combinatorics, Information Processing 65 (Proceedings of the 1965 IFIP Congress), 497–498, 1966.</ref><ref name="Wells1971">Mark Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford, 1971.</ref>
|-
| style="text-align:right;" | 13
| style="text-align:right;" | 33
| style="text-align:center;" | 34 <ref name="KasaiSawatoIwata1994">Takumi Kasai, Shusaku Sawato, Shigeki Iwata, Thirty four comparisons are required to sort 13 items, LNCS 792, 260-269, 1994.</ref><ref name="Peczarski2002">Marcin Peczarski, Sorting 13 elements requires 34 comparisons, LNCS 2461, 785–794, 2002.</ref><ref name="Peczarski2004">Marcin Peczarski, New results in minimum-comparison sorting, Algorithmica 40 (2), 133–145, 2004.</ref>
|-
| style="text-align:right;" | 14
| style="text-align:right;" | 37
| style="text-align:center;" | 38 <ref name="Peczarski2004" />
|-
| style="text-align:right;" | 15
| style="text-align:right;" | 41
| style="text-align:center;" | 42 <ref name="Peczarski2006">Marcin Peczarski, Computer assisted research of posets, PhD thesis, University of Warsaw, 2006.</ref><ref name="Peczarski2007">{{استشهاد بدورية محكمة
| الأخير = Peczarski
| الأول = Marcin
| سنة = 2007
| عنوان = The Ford-Johnson algorithm is still unbeaten for less than 47 elements
| صحيفة = Inf. Process. Lett.
| المجلد = 101
| العدد = 3
| صفحات = 126–128
| DOI = 10.1016/j.ipl.2006.09.001
}}</ref><ref name="ChengLiuWang2007">{{استشهاد بدورية محكمة
| الأول = Weiyi
| الأخير = Cheng
| مؤلف2-الأول = Xiaoguang
| مؤلف2-الأخير = Liu
| مؤلف3-الأول = Gang
| مؤلف3-الأخير = Wang
| مؤلف4-الأول = Jing
| مؤلف4-الأخير = Liu
| تاريخ = October 2007
| عنوان = 最少比较排序问题中S（15）和S（19）的解决
| لغة = zh
| trans_title = The results of S(15) and S(19) to minimum-comparison sorting problem
| مسار = http://fcst.ceaj.org/EN/abstract/abstract47.shtml
| صحيفة = Journal of Frontiers of Computer Science and Technology
| المجلد = 1
| العدد = 3
| صفحات = 305–313
| مسار أرشيف = https://web.archive.org/web/20221111073418/http://fcst.ceaj.org/EN/abstract/abstract47.shtml | تاريخ أرشيف = 11 نوفمبر 2022 }}</ref>
|-
| style="text-align:right;" | 16
| style="text-align:right;" | 45
| 45 أو 46 <ref>{{استشهاد بدورية محكمة
| الأخير = Peczarski
| الأول = Marcin
| عنوان = Towards Optimal Sorting of 16 Elements
| صحيفة = Acta Universitatis Sapientiae
| المجلد = 4
| العدد = 2
| صفحات = 215–224
| تاريخ = 3 August 2011
| arxiv = 1108.0866
| bibcode = 2011arXiv1108.0866P
}}</ref>
|-
| style="text-align:right;" | 17
| style="text-align:right;" | 49
| 49 أو 50
|-
| style="text-align:right;" | 18
| style="text-align:right;" | 53
| 53 أو 54
|-
| style="text-align:right;" | 19
| style="text-align:right;" | 57
| style="text-align:center;" | 58 <ref name="ChengLiuWang2007" />
|-
| style="text-align:right;" | 20
| style="text-align:right;" | 62
| style="text-align:center;" | 62
|-
| style="text-align:right;" | 21
| style="text-align:right;" | 66
| style="text-align:center;" | 66
|-
| style="text-align:right;" | 22
| style="text-align:right;" | 70
| style="text-align:center;" | 71 <ref name="Peczarski2004" /> 
|-
| colspan="3" style="height:5px;" | '''------ الجزء الثاني-------'''
|-
! ''n''
! <math>\left\lceil\log_2(n!)\right\rceil</math>
! <math>n \log_2 n - \frac{n}{\ln 2}</math>
|-
| style="text-align:right;" | 10
| style="text-align:right;" | 22
| style="text-align:center;" | 19
|-
| style="text-align:right;" | 100
| style="text-align:right;" | 525
| style="text-align:center;" | 521
|-
| style="text-align:right;" | 1000
| style="text-align:right;" | 8530
| style="text-align:center;" | 8524
|-
| style="text-align:right;" | 10000
| style="text-align:right;" | 118,459
| style="text-align:center;" | 118,451
|-
| style="text-align:right;" | 100000
| style="text-align:right;" | 1,516,705
| style="text-align:center;" | 1,516,695
|-
| style="text-align:right;" | {{بدون لف|1,000,000}}
| style="text-align:right;" | 18,488,885
| style="text-align:center;" | 18,488,874
|-
| colspan="3" |الجزء الأول: مقارنة بين الحد الأدنى لعدد المقارنات باستخدام المعادلة التالية: <math>\left\lceil\log_2(n!)\right\rceil</math>، والعدد الأدنى الفعلي (المصدر:OEIS:A036604) لعدد المقارنات المطلوبة لترتيب قائمة ''مكونة من'' n من العناصر (في أسوأ حالة).

الجزء الثاني من الجدول قرب الحد الأدنى لعدد المقارنات المطلوبة باستخدام [[تقريب ستيرلينغ|تقريب ستيرلنغ]] تقريبا جيدا باستخدام المعادلة التالية:<math>n \log_2 n - \frac{n}{\ln 2}</math>
|}
مثال: إذا كانت n=10 , فإن الحد الأدنى يساوي 22, والحد الأدنى الفعلي يساوي أيضا 22, بينما باستخدام تقريب ستيرلينغ، فإن الحد الأدنى (مقرّب باستخدام المعادلة) يساوي 19.عدد المقارنات التي تتطلبها خوارزميات الترتيب بالمقارنة تزداد بالتناسب مع <math>n\log(n)</math>، حيث أن <math>n</math> هو عدد العناصر المطلوب ترتيبها. هذا الحد هو حد [[محكم بشكل مقارب]].

إذا كان لدينا مجموعة من الأعداد المختلفة (يمكننا افتراض هذا الإختلاف لأن هذا الإختلاف هو تحليل لأسوأ حالة)، فهناك عدد من [[البدائل]] يساوي [[عاملي|مضروب]] حجم القائمة (!<math>n</math>)، واحد منها فقط يمثل القائمة بالترتيب المطلوب.

مثال: لو كان هناك قائمة مكونة من ثلاثة عناصر n=3 وقيمها {1,2,3}، فإن عدد البدائل يساوي !3 ويساوي 6 بدائل، هذه البدائل هي: {1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,2,1} {3,1,2}.

يجب أن تحصل خوارزمية الترتيب على معلومات كافية من عمليات المقارنات لتحديد البديل الصحيح. إذا كانت الخوارزمية تنهي عملها دائمًا بعد <math>f(n)</math> من الخطوات على الأكثر، فإنه لا يمكن لها تمييز أكثر من <math>2^{f(n)}</math> من الحالات لأن العناصر جميعها مميزة ولأن كل مقارنة لها نتيجتين محتملتين فقط. وبالتالي:

: <math>2^{f(n)}\geq n!</math>
: أو بشكل مكافئ
: <math>f(n)\geq\log_2(n!).</math>

بالنظر إلى أول <math>n/2</math> من عوامل (!<math>n</math>)

<math>n! = n (n-1) \cdots 1</math> نحصل على:

<math>\log_2(n!) \geq \log_2\left(\left(\frac{n}{2}\right)^\frac{n}{2}\right) = \frac{n}{2} \frac{\log n}{\log 2} - \frac{n}{2} = \Theta(n \log n).</math>

: <math>\log_2(n!) = \Omega(n \log n).</math>

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

حد أعلى مطابق للحد الأدنى أعلاه يأتي من وجود الخوارزميات التي تحقق هذا الحد في أسوأ الحالات، مثل خوارزميتي [[تصنيف دمجي|ترتيب الدمج]] و[[تصنيف الكومة|ترتيب الكومة]]. النقاش أعلاه يعطي حدًا أدنى ''مطلقًا''، وليس فقط حدًا مقاربًا، لعدد المقارنات، تحديدا <math>\left\lceil\log_2(n!)\right\rceil</math> من المقارنات. هذا الحد الأدنى جيد إلى حد مقبول (يمكن الوصول إليه بتفاوت خطي من خلال خوارزمية ترتيب الدمج)، ولكن من المعروف أنه غير دقيق. فمثلا،

<math>\left\lceil\log_2(13!)\right\rceil = 33</math>

علما بأنه أقل عدد مثبت من المقارنات لترتيب 13 عنصرًا هو 34 عملية مقارنة.

إن تحديد العدد ''الفعلي'' للمقارنات اللازمة لترتيب عدد معين من العناصر هي مشكلة حسابية صعبة حتى بالنسبة لـعدد قليل من العناصر ''n''، ولا توجد صيغة رياضية بسيطة معروفة للحل. للإطلاع على بعض القيم التي تم حسابها، انظر إلى OEIS:A036604.

=== الحد الأدنى لمعدل عدد المقارنات ===
ينطبق حد مماثل على متوسط عدد المقارنات. على فرض أن:

* جميع القيم مميزة، أي أن كل مقارنة ستعطي إما ''a'' > ''b'' أو ''a'' < ''b''، و
* القيم المدخلة عبارة عن بديل عشوائي، تم اختياره من مجموعة البدائل الممكنة لعناصر''n''،

من المستحيل تحديد ما هو ترتيب القيم المدخلة من خلال عمل مجموعة من المقارنات أقل من {{تعبير رياضي|log<sub>2</sub>(''n''!)}} في المتوسط. يمكن معرفة هذا الأمر بسهولة باستخدام بعض مفاهيم من [[نظرية المعلومات]]. نظرية [[اعتلاج (نظرية المعلومات)|الاعتلاج]] من هذا التبديل العشوائي هو {{تعبير رياضي|log<sub>2</sub>(''n''!)}} بت. وكون عملية المقارنة تعطي نتيجتين فقط، فإن الحد الأقصى لكمية المعلومات التي تمنحها هذه العملية هو 1 بت. وبالتالي، بعد ''k'' من المقارنات، الإنتروبيا المتبقية من التبديل، نظرا لنتائج تلك المقارنات، هي على الأقل {{تعبير رياضي|log<sub>2</sub>(''n''!)&nbsp;−&nbsp;''k''}} بت في المتوسط. للقيام بعملية الترتيب، يجب أن تتوفر معلومات كاملة، لذلك يجب أن تكون الانتروبيا المتبقية هي 0. بناء على ذلك فإن ''k'' يجب أن تكون على الأقل {{تعبير رياضي|log<sub>2</sub>(''n''!)}} في المتوسط.

يطلق على الحد الأدنى المشتق باستخدام نظرية المعلومات اسم «الحد الأدنى النظري». هذا الحد صحيح ولكنه ليس بالضرورة الحد الأدنى الأدقّ. وفي بعض الحالات، قد يكون الحد الأدنى النظري لمشكلة ما بعيدا عن الحد الأدنى الفعلي لنفس المشكلة. على سبيل المثال، الحد الأدنى النظري للإختيار هو <math>\left\lceil\log_2(n)\right\rceil</math> بينما هناك حاجة إلى إجراء <math>n-1</math> من المقارنات حسب رأي مخالف. يشبه التفاعل بين الحد الأدنى النظري لنظرية المعلومات والحد الأدنى الفعلي، إلى حد كبير، اقتران ذا قيمة حقيقية يحدّ اقتران ذا قيمة صحيحة حدّا أدنى. على الرغم من ذلك، فإن هذا ليس صحيحا تماما عند الأخذ بعين الإعتبار الحالة المتوسطة.

لمعرفة ما يحصل خلال تحليل الحالة المتوسطة، يجب تحديد ما الذي يشير إليه مصطلح «المتوسطة»؟ ما هو المطلوب حساب المتوسط له؟ مع بعض المعرفة بنظرية المعلومات، فإن الحالة المتوسطة عبارة عن متوسطات الحد الأدنى على جميع التباديل ككل. إلا أن أي خوارزمية حاسوبية (حسب ما يعتقد حاليًا) يجب أن تتعامل مع كل تبديل كمثال فردي للمشكلة. وبالتالي، فإن متوسط الحد الأدنى الذي نبحث عنه يتم حسابه على مستوى جميع الحالات الفردية.

للبحث عن الحد الأدنى فيما يتعلق ب الإمكانيات المحدودة للحاسبات، يمكننا الإعتماد على [[نموذج شجرة القرار]]. دعنا نعيد صياغة ما نريد تحقيقه مرة أخرى. في نموذج شجرة القرار، الحد الأدنى الذي نريد توضيحه هو الحد الأدنى لمتوسط أطوال المسارات من الجذر"tree root" (رأس شجرة القرار ثنائية الأوراق) إلى <math>n!</math> من الأوراق "tree leaves" (نهايات شجرة القرار ثنائية الأوراق) حيث تمثل كل ورقة إحدى التباديل المحتملة. من المقنع أن نقول أنّ الشجرة الثنائية المتوازنة والكاملة تحقق الحد الأدنى لمتوسط الأطوال سالفة الذكر. مع بعض الحسابات الدقيقة، لشجرة ثنائية كاملة متوازنة تحوي <math>n!</math> من الأوراق، فإن متوسط أطوال مسارات الجذر إلى الأوراق يمكن حسابه كالاتي:

: <math>\frac{(2n! - 2^{\lfloor \log_2 n! \rfloor + 1}) \cdot \lceil \log_2 n! \rceil + (2^{\lfloor \log_2 n! \rfloor + 1} - n!) \cdot \lfloor \log_2 n! \rfloor}{n!}</math>

على سبيل المثال، إذا كانت {{تعبير رياضي|1=''n''&nbsp;=&nbsp;3}}، فإن الحد الأدنى النظري في الحالة المتوسطة يساوي 2.58، في حين أن متوسط الحد الأدنى حسب نموذج شجرة القرار هو 8/3، ويساوي تقريبا 2.67.

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

=== n log n الحد الأقصى لعدد المقارنات لمصفوفة حجمها على شكل 2<sup>k</sup> ===
يمكن أن يحسب بسهولة لخوارزمية حقيقية "sorted-list-merging" (يتم ترتيب المصفوفة على شكل n من الكتل بحجم 1، ودمجها مع 1-1 إلى 2، ودمج 2-2 إلى 4. . . الخ).

<pre>
(1) = = = = = = = =

(2) =   =   =   =     // مقارنة وحدة على الأكثر مكررة أربع مرات لدمج 4 صفوف بحجم 1
   === === === ===

(3)   =       =       // سبع مقارنات على الأكثر مكررة لدمج 4 صفوف بحجم 2
     ===     ===  
    =====   ===== 
   ======= =======

(4)                   // خمس عشر مقارنة على الأكثر مكررة مرة واحدة لدمج صفيين بحجم 4

الصيغة المستخرجة:
n = 256 = 2^8 (للتبسيط نمثل حجم المصفوفة ل شكل 2^k)
On = (n-1) + 2(n/2-1) + 4(n/4-1) + 8(n/8-1) + 16(n/16-1) + 32(n/32-1) + 64(n/64-1) + 128(n/128-1)
On = (n-1) + (n-2) + (n-4) + (n-8) + (n-16) + (n-32) + (n-64) + (n-128)
On = n+n+n+n+n+n+n+n - (1+2+4+8+16+32+64+128)   | 1+2+4... = formula for geometric sequence Sn = a1 * (q^i - 1) / (n - 1), n تمثل عدد العناصر، تمثل العنصر الأول
On = 8*n - 1 * (2^8 - 1) / (2 - 1)
On = 8*n - (2^8 - 1)   | 2^8 = n
On = 8*n - (n - 1)
On = (8-1)*n + 1   | 8 = ln(n)/ln(2) = ln(256)/ln(2)
On = (ln(n)/ln(2) - 1) * n + 1

مثال:
n = 2^4 = 16, On ~= 3*n
n = 2^8 = 256, On ~= 7*n
n = 2^10 = 1.024, On ~= 9*n
n = 2^20 = 1.048.576, On ~= 19*n
</pre>

=== فرز قائمة مرتبة مسبقًا ===
إذا كانت القائمة مرتبة نسبيا، فإنه يمكن أن يكون عدد المقارنات المطلوبة لترتيبها أقل وفقًا لبعض مقاييس الترتيب. تمتاز خوارزمية الترتيب التكيفي بهذه الخاصية؛ خاصية «الترتيب المسبق»، وتعمل بسرعة أكبر على المدخلات شبه المرتبة، غالبًا مع بقاء حاجتها إلى <math>O(n\log n)</math> من الوقت في أسوأ حالة. مثال على ذلك خوارزمية [[:en:Adaptive heap sort|ترتيب الكومة التكيفي]]، وهي خوارزمية ترتيب تعتمد على [[الأشجار الديكارتية]]. تحتاج إلى <math>O(n\log k)</math> من الوقت، حيث أن <math>k</math> هو المتوسط (على كل القيم <math>x</math> في التسلسل) لعدد المرات التي يقفز فيها التسلسل من أقل من <math>x</math> إلى أكبر من <math>x</math> أو العكس.<ref>{{استشهاد|الأخير=Levcopoulos|الأول=Christos|مؤلف2-الأخير=Petersson|مؤلف2-الأول=Ola|الفصل=Heapsort - Adapted for Presorted Files|DOI=10.1007/3-540-51542-9_41|مكان=London, UK|صفحات=499–509|ناشر=Springer-Verlag|سلسلة=Lecture Notes in Computer Science|عنوان=WADS '89: Proceedings of the Workshop on Algorithms and Data Structures|المجلد=382|سنة=1989}}.</ref>

== ملحوظات ==
{{مراجع}}

== مراجع ==

* [[دونالد كينوث|دونالد كنوث]]. ''[[فن برمجة الحاسوب|فن برمجة الكمبيوتر]]''، المجلد 3: ''الفرز والبحث''، الإصدار الثاني. أديسون ويسلي، 1997.{{ردمك|0-201-89685-0}}[[النظام القياسي الدولي لترقيم الكتب|رقم ISBN]]&nbsp;[[خاص:BookSources/0-201-89685-0|0-201-89685-0]] . القسم 5.3.1: الفرز الأدنى مقارنة، ص.&nbsp;180–197.
{{خوارزميات الترتيب}}
{{شريط بوابات|رياضيات|علم الحاسوب|علوم}}

[[تصنيف:خوارزميات ترتيب]]