الترتيب بالمقارنة

هذه المقالة بحاجة لصندوق معلومات. فضلًا ساعد في تحسين هذه المقالة بإضافة صندوق معلومات مخصص إليها.

تحوي هذه المقالة أو هذا القسم ترجمة آلية. فضلًا، ساهم في تدقيقها وتحسينها أو إزالتها لأنها تخالف سياسات ويكيبيديا. (نقاش)

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (نوفمبر 2022)

الترتيب بالمقارنة (بالإنجليزية: Comparison sort)‏ هو نوع من أنواع خوارزميات الترتيب التي تعتمد في عملها لترتيب عناصر قائمة ما على إجراء عملية مقارنة (غالبًا عملية «أقل من أو يساوي» أو مقارنة ثلاثية)، وتحدّد هذه المقارنة أي من العنصرين قيد المقارنة يجب أن يظهر أولاً في القائمة النهائية المرتبة. المتطلب الوحيد هو أن تقوم عملية المقارنة بعمل إعادة ترتيب للبيانات مع الأخذ بعين الإعتبار:

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

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

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

القائمة التالية تتضمن بعض أنواع المقارنة الأكثر شهرة:

• الترتيب السريع
• ترتيب الكومة
• ترتيب القذائف
• ترتيب الدمج
• ترتيب المقدمة
• ترتيب الإدراج
• ترتيب الإختيار
• ترتيب الفقاعة
• ترتيب الفردي الزوجي
• ترتيب كوكتيل شاكر
• ترتيب الدورة
• ترتيب الفرز والإدماج
• ترتيب سلس
• ترتيب تيم
• ترتيب الكتلة

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

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

قد تعمل بعض خوارزميات الترتيب بالمقارنة بشكل أسرع في بعض القوائم؛ تحتاج العديد من خوارزميات الترتيب التكيفي مثل خوارزمية ترتيب الإدراج للتشغيل إلى O(n) من الوقت لترتيب مجموعة من العناصر في قائمة مرتبة بشكل كامل أو شبه مرتبة. وينطبق الحد الأدنى Ω(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)

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

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

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

إن مشكلة فرز أزواج الأرقام غير خاضعة للحد الأدنى Ω(n² log n) (التربيع في n² ناتج عن عملية بناء الأزواج)؛ الخوارزمية الأكثر شيوعا تحتاج إلى وقت تشغيل O(n² log n)، فقط O(n²) من المقارنات.

n	${\displaystyle \left\lceil \log _{2}(n!)\right\rceil }$	الحد الأدنى
1	0	0
2	1	1
3	3	3
4	5	5
5	7	7
6	10	10
7	13	13
8	16	16
9	19	19
10	22	22
11	26	26
12	29	30 [1][2]
13	33	34 [3][4][5]
14	37	38 [5]
15	41	42 [6][7][8]
16	45	45 أو 46 [9]
17	49	49 أو 50
18	53	53 أو 54
19	57	58 [8]
20	62	62
21	66	66
22	70	71 [5]
------ الجزء الثاني-------
n	${\displaystyle \left\lceil \log _{2}(n!)\right\rceil }$	${\displaystyle n\log _{2}n-{\frac {n}{\ln 2}}}$
10	22	19
100	525	521
1000	8530	8524
10000	118,459	118,451
100000	1,516,705	1,516,695
1,000,000	18,488,885	18,488,874
الجزء الأول: مقارنة بين الحد الأدنى لعدد المقارنات باستخدام المعادلة التالية: ${\displaystyle \left\lceil \log _{2}(n!)\right\rceil }$، والعدد الأدنى الفعلي (المصدر:OEIS:A036604) لعدد المقارنات المطلوبة لترتيب قائمة مكونة من n من العناصر (في أسوأ حالة). الجزء الثاني من الجدول قرب الحد الأدنى لعدد المقارنات المطلوبة باستخدام تقريب ستيرلنغ تقريبا جيدا باستخدام المعادلة التالية:${\displaystyle n\log _{2}n-{\frac {n}{\ln 2}}}$

مثال: إذا كانت n=10 , فإن الحد الأدنى يساوي 22, والحد الأدنى الفعلي يساوي أيضا 22, بينما باستخدام تقريب ستيرلينغ، فإن الحد الأدنى (مقرّب باستخدام المعادلة) يساوي 19.عدد المقارنات التي تتطلبها خوارزميات الترتيب بالمقارنة تزداد بالتناسب مع ${\displaystyle n\log(n)}$، حيث أن ${\displaystyle n}$ هو عدد العناصر المطلوب ترتيبها. هذا الحد هو حد محكم بشكل مقارب.

إذا كان لدينا مجموعة من الأعداد المختلفة (يمكننا افتراض هذا الإختلاف لأن هذا الإختلاف هو تحليل لأسوأ حالة)، فهناك عدد من البدائل يساوي مضروب حجم القائمة (!${\displaystyle n}$)، واحد منها فقط يمثل القائمة بالترتيب المطلوب.

مثال: لو كان هناك قائمة مكونة من ثلاثة عناصر 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}.

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

${\displaystyle 2^{f(n)}\geq n!}$

أو بشكل مكافئ

${\displaystyle f(n)\geq \log _{2}(n!).}$

بالنظر إلى أول ${\displaystyle n/2}$ من عوامل (!${\displaystyle n}$)

${\displaystyle n!=n(n-1)\cdots 1}$ نحصل على:

${\displaystyle \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).}$

${\displaystyle \log _{2}(n!)=\Omega (n\log n).}$

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

حد أعلى مطابق للحد الأدنى أعلاه يأتي من وجود الخوارزميات التي تحقق هذا الحد في أسوأ الحالات، مثل خوارزميتي ترتيب الدمج وترتيب الكومة. النقاش أعلاه يعطي حدًا أدنى مطلقًا، وليس فقط حدًا مقاربًا، لعدد المقارنات، تحديدا ${\displaystyle \left\lceil \log _{2}(n!)\right\rceil }$ من المقارنات. هذا الحد الأدنى جيد إلى حد مقبول (يمكن الوصول إليه بتفاوت خطي من خلال خوارزمية ترتيب الدمج)، ولكن من المعروف أنه غير دقيق. فمثلا،

${\displaystyle \left\lceil \log _{2}(13!)\right\rceil =33}$

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

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

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

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

من المستحيل تحديد ما هو ترتيب القيم المدخلة من خلال عمل مجموعة من المقارنات أقل من log₂(n!) في المتوسط. يمكن معرفة هذا الأمر بسهولة باستخدام بعض مفاهيم من نظرية المعلومات. نظرية الاعتلاج من هذا التبديل العشوائي هو log₂(n!) بت. وكون عملية المقارنة تعطي نتيجتين فقط، فإن الحد الأقصى لكمية المعلومات التي تمنحها هذه العملية هو 1 بت. وبالتالي، بعد k من المقارنات، الإنتروبيا المتبقية من التبديل، نظرا لنتائج تلك المقارنات، هي على الأقل log₂(n!) − k بت في المتوسط. للقيام بعملية الترتيب، يجب أن تتوفر معلومات كاملة، لذلك يجب أن تكون الانتروبيا المتبقية هي 0. بناء على ذلك فإن k يجب أن تكون على الأقل log₂(n!) في المتوسط.

يطلق على الحد الأدنى المشتق باستخدام نظرية المعلومات اسم «الحد الأدنى النظري». هذا الحد صحيح ولكنه ليس بالضرورة الحد الأدنى الأدقّ. وفي بعض الحالات، قد يكون الحد الأدنى النظري لمشكلة ما بعيدا عن الحد الأدنى الفعلي لنفس المشكلة. على سبيل المثال، الحد الأدنى النظري للإختيار هو ${\displaystyle \left\lceil \log _{2}(n)\right\rceil }$ بينما هناك حاجة إلى إجراء ${\displaystyle n-1}$ من المقارنات حسب رأي مخالف. يشبه التفاعل بين الحد الأدنى النظري لنظرية المعلومات والحد الأدنى الفعلي، إلى حد كبير، اقتران ذا قيمة حقيقية يحدّ اقتران ذا قيمة صحيحة حدّا أدنى. على الرغم من ذلك، فإن هذا ليس صحيحا تماما عند الأخذ بعين الإعتبار الحالة المتوسطة.

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

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

${\displaystyle {\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!}}}$

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

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

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

(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

إذا كانت القائمة مرتبة نسبيا، فإنه يمكن أن يكون عدد المقارنات المطلوبة لترتيبها أقل وفقًا لبعض مقاييس الترتيب. تمتاز خوارزمية الترتيب التكيفي بهذه الخاصية؛ خاصية «الترتيب المسبق»، وتعمل بسرعة أكبر على المدخلات شبه المرتبة، غالبًا مع بقاء حاجتها إلى ${\displaystyle O(n\log n)}$ من الوقت في أسوأ حالة. مثال على ذلك خوارزمية ترتيب الكومة التكيفي، وهي خوارزمية ترتيب تعتمد على الأشجار الديكارتية. تحتاج إلى ${\displaystyle O(n\log k)}$ من الوقت، حيث أن ${\displaystyle k}$ هو المتوسط (على كل القيم ${\displaystyle x}$ في التسلسل) لعدد المرات التي يقفز فيها التسلسل من أقل من ${\displaystyle x}$ إلى أكبر من ${\displaystyle x}$ أو العكس.^[10]

• دونالد كنوث. فن برمجة الكمبيوتر، المجلد 3: الفرز والبحث، الإصدار الثاني. أديسون ويسلي، 1997.(ردمك 0-201-89685-0)رقم ISBN 0-201-89685-0 . القسم 5.3.1: الفرز الأدنى مقارنة، ص. 180–197.