فرز المقارنة

فرز المقارنة هو نوع من خوارزميات الفرز التي تقرأ عناصر القائمة من خلال عملية مقارنة مجردة واحدة (غالبًا ما تكون عامل "أصغر من أو يساوي" أو مقارنة ثلاثية ) لتحديد أي عنصرين يجب أن يظهر أولًا في القائمة النهائية المرتبة. الشرط الوحيد هو أن يُشكّل العامل ترتيبًا مسبقًا كليًا للبيانات؛ أي:

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

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

تُعتبر خوارزميات فرز المقارنة التي دُرست في الأدبيات "خوارزميات قائمة على المقارنة". ^{[ 1 ]} لا يُمكن للخوارزمية تبديل العنصرين a و b أو إعادة ترتيبهما إلا بعد تحديد الترتيب بينهما بناءً على نتائج مقارنات سابقة. ويتحقق ذلك عندما يُمكن استنتاج الترتيب بين a و b من خلال الإغلاق المتعدي لنتائج هذه المقارنات السابقة.

في عمليات الفرز القائمة على المقارنة، يعتمد قرار تنفيذ العمليات الأساسية الأخرى غير المقارنات على نتائج المقارنات. لذا، في تحليل الوقت، يُستخدم عدد المقارنات المنفذة لتحديد تقديرات الحد الأعلى لعدد العمليات الأساسية المنفذة، مثل عمليات التبديل أو الإسناد. ^{[ 1 ]}

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

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

• فرز سريع
• فرز الكومة
• شلسورت
• فرز الدمج
• إنتروسورت
• فرز الإدراج
• فرز التحديد
• فرز الفقاعات
• فرز فردي-زوجي
• نوع من أنواع خلاطات الكوكتيل
• فرز الدورة
• فرز الدمج والإدراج
• سموث سورت
• تيمسورت
• فرز الكتل

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

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

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

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

دالة tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc)) إذا كان lefta ≠ righta، تُرجع الدالة compare(lefta, righta) وإلا إذا كان leftb ≠ rightb، تُرجع الدالة compare(leftb, rightb) وإلا تُرجع الدالة compare(leftc, rightc)

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

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

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

إن مشكلة فرز أزواج الأرقام حسب مجموعها لا تخضع للحد Ω( n ² log n ) أيضًا (المربع الناتج عن الاقتران)؛ لا تزال أفضل خوارزمية معروفة تستغرق وقتًا قدره O( n ² log n ) ، ولكن فقط O( 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 [ 3 ] [ 4 ]
13	33	34 [ 5 ] [ 6 ] [ 7 ]
14	37	38 [ 7 ]
15	41	42 [ 8 ] [ 9 ] [ 10 ]
16	45	46 [ 11 ]
17	49	50 [ 11 ]
18	53	54 [ 11 ]
19	57	58 [ 10 ]
20	62	62
21	66	66
22	70	71 [ 7 ]
ن	${\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
مليون	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}}}$.

يزداد عدد المقارنات التي تتطلبها خوارزمية فرز المقارنة بما يتناسب مع${\displaystyle n\log(n)}$حيث n هو عدد العناصر المراد فرزها. هذا الحد محكم تقاربياً .

بافتراض وجود قائمة من الأرقام المميزة (يمكننا افتراض ذلك لأن هذا تحليل لأسوأ الحالات)، يوجد n تبديلًا مضروبيًا، واحد منها فقط هو القائمة مرتبة. يجب أن تحصل خوارزمية الفرز على معلومات كافية من المقارنات لتحديد التبديل الصحيح. إذا كانت الخوارزمية تُنهي عملها دائمًا بعد n تبديلًا مضروبيًا على الأكثر${\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!=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  .

(1) = = = = = = = = (2) = = = = // الحد الأقصى 1 يقارن (الحجم1+الحجم2-1)، 4x يكرر لدمج 8 مصفوفات بحجم 1 و1 === === === === (3) = = // الحد الأقصى 7 مقارنات، 2x تكرار لدمج 4 مصفوفات بحجم 2 و2 === === ===== ===== ======= ======= (4) // الحد الأقصى 15 مقارنة، تكرار واحد لدمج مصفوفتين بحجم 4 و4 استخلاص الصيغة: n = 256 = 2^8 (حجم المصفوفة بالصيغة 2^k، للتبسيط) على = (ن-1) + 2(ن/2-1) + 4(ن/4-1) + 8(ن/8-1) + 16(ن/16-1) + 32(ن/32-1) + 64(ن/64-1) + 128(ن/128-1) على = (ن-1) + (ن-2) + (ن-4) + (ن-8) + (ن-16) + (ن-32) + (ن-64) + (ن-128) On = n+n+n+n+n+n+n+n - (1+2+4+8+16+32+64+128) | 1+2+4... = صيغة المتتابعة الهندسية Sn = a1 * (q^i - 1) / (n - 1)، حيث n هو عدد العناصر، وa1 هو العنصر الأول على = 8*ن - 1 * (2^8 - 1) / (2 - 1) على = 8*ن - (2^8 - 1) | 2^8 = ن 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 مثال: ن = ٢^٤ = ١٦، أون ≈ ٣*ن ن = 2^8 = 256، أون ≈ 7*ن n = 2^10 = 1.024، On ≈ 9*n ن = 2^20 = 1.048.576، على ~= 19*ن 

• كنوت، دونالد إي. (24 أبريل 1998). "5.3.1: فرز المقارنة الدنيا". فن برمجة الحاسوب . المجلد  الثالث. الفرز والبحث (  الطبعة الثانية). الولايات المتحدة الأمريكية: شركة أديسون-ويسلي لونغمان للنشر. الصفحات 180-197 . ISBN  978-0-201-89685-5.