فرز بالمقارنة
المحتويات

على سبيل التعريف، الترتيب بالمقارنة هو نوع من أنواع خوارزميات الترتيب التي تعتمد في عملها لترتيب عناصر قائمة ما على إجراء عملية مقارنة (غالبًا عملية «أقل من أو يساوي» أو مقارنة ثلاثية)، وتحدّد هذه المقارنة أي من العنصرين قيد المقارنة يجب أن يظهر أولاً في القائمة النهائية المرتبة. المتطلب الوحيد هو أن تقوم عملية المقارنة بعمل إعادة ترتيب للبيانات مع الأخذ بعين الاعتبار:
وفي السياق ذاته، طريقة الترتيب بالمقارنة يمكن التفكير بها على أنها استخدام شخصا ما لمقياس توازن ولديه مجموعة من الأوزان غير محددة الوزن سابقا، هدفهه هو ترتيب الأوزان بالترتيب الصحيح حسب وزنهم دون أي معلومات باستثناء تلك التي تم الحصول عليها عن طريق وضع اثنين من الأوزان على الميزان ومعرفة أيهما أثقل (أو إذا كان وزنهما متماثلا).
إذا كانت a ≤ b وكانت b ≤ c فإن a ≤ c (علاقة التعدي)
لكل من a و b، فإن: a ≤ b أو b ≤ a (علاقة الإرتباط).
وفي هذا السياق، من الممكن أن يكون كلا من a ≤ b و b ≤ a صحيح؛ في هذه الحالة لا بد أن يكون العنصرين متساويين في القيمة، وقد يأتي أي منهما أولاً في القائمة المرتبة. في خوارزمية الترتيب المتّسمة بالثبات، يحدد ترتيب المدخلات ترتيب ظهور أي من العنصرين a أو b أولا في القائمة المرتبة.
الحد الأدنى لمعدل عدد المقارنات
إضافةً إلى ذلك، يطلق على الحد الأدنى المشتق باستخدام نظرية المعلومات اسم «الحد الأدنى النظري». هذا الحد صحيح ولكنه ليس بالضرورة الحد الأدنى الأدقّ. وفي بعض الحالات، قد يكون الحد الأدنى النظري لمشكلة ما بعيدا عن الحد الأدنى الفعلي لنفس المشكلة. مثلًا، الحد الأدنى النظري للإختيار هو بينما هناك حاجة إلى إجراء من المقارنات حسب رأي مخالف. يشبه التفاعل بين الحد الأدنى النظري لنظرية المعلومات والحد الأدنى الفعلي، إلى حد كبير، اقتران ذا قيمة حقيقية يحدّ اقتران ذا قيمة صحيحة حدّا أدنى. على الرغم من ذلك، فإن هذا ليس صحيحا تماما عند الأخذ بعين الإعتبار الحالة المتوسطة.
من جانب آخر، (2) = = = = // مقارنة وحدة على الأكثر مكررة أربع مرات لدمج 4 صفوف بحجم 1
كذلك، القيم المدخلة عبارة عن بديل عشوائي، تم اختياره من مجموعة البدائل الممكنة لعناصرn،
من جانب آخر، من المستحيل تحديد ما هو ترتيب القيم المدخلة من خلال عمل مجموعة من المقارنات أقل من في المتوسط. يمكن معرفة هذا الأمر بسهولة باستخدام بعض مفاهيم من نظرية المعلومات. نظرية الاعتلاج من هذا التبديل العشوائي هو بت. وكون عملية المقارنة تعطي نتيجتين فقط، فإن الحد الأقصى لكمية المعلومات التي تمنحها هذه العملية هو 1 بت. وبالتالي، بعد k من المقارنات، الإنتروبيا المتبقية من التبديل، نظرا لنتائج تلك المقارنات، هي على الأقل بت في المتوسط. للقيام بعملية الترتيب، يجب أن تتوفر معلومات كاملة، لذلك يجب أن تكون الانتروبيا المتبقية هي 0. بناء على ذلك فإن k يجب أن تكون على الأقل في المتوسط.
من جهة ثانية، يمكن أن يحسب بسهولة لخوارزمية حقيقية "sorted-list-merging" (يتم ترتيب المصفوفة على شكل n من الكتل بحجم 1، ودمجها مع 1-1 إلى 2، ودمج 2-2 إلى 4. . . الخ).
كذلك، للبحث عن الحد الأدنى فيما يتعلق ب الإمكانيات المحدودة للحاسبات، يمكننا الإعتماد على نموذج شجرة القرار. دعنا نعيد صياغة ما نريد تحقيقه مرة أخرى. في نموذج شجرة القرار، الحد الأدنى الذي نريد توضيحه هو الحد الأدنى لمتوسط أطوال المسارات من الجذر"tree root" (رأس شجرة القرار ثنائية الأوراق) إلى من الأوراق "tree leaves" (نهايات شجرة القرار ثنائية الأوراق) حيث تمثل كل ورقة إحدى التباديل المحتملة. من المقنع أن نقول أنّ الشجرة الثنائية المتوازنة والكاملة تحقق الحد الأدنى لمتوسط الأطوال سالفة الذكر. مع بعض الحسابات الدقيقة، لشجرة ثنائية كاملة متوازنة تحوي من الأوراق، فإن متوسط أطوال مسارات الجذر إلى الأوراق يمكن حسابه كالاتي:
(1) = = = = = = =
ومن جهة أخرى، جميع القيم مميزة، أي أن كل مقارنة ستعطي إما a > b أو a < b، و
وفي هذا الصدد، مثلًا، إذا كانت ، فإن الحد الأدنى النظري في الحالة المتوسطة يساوي 2.58، في حين أن متوسط الحد الأدنى حسب نموذج شجرة القرار هو 8/3، ويساوي على وجه التقريب 2.67.
ينطبق حد مماثل على متوسط عدد المقارنات. على فرض أن:
من جانب آخر، لمعرفة ما يحصل خلال تحليل الحالة المتوسطة، يجب تحديد ما الذي يشير إليه مصطلح «المتوسطة»؟ ما هو المطلوب حساب المتوسط له؟ مع بعض المعرفة بنظرية المعلومات، فإن الحالة المتوسطة عبارة عن متوسطات الحد الأدنى على جميع التباديل ككل. إلا أن أي خوارزمية حاسوبية (حسب ما يعتقد في الوقت الحالي) يجب أن تتعامل مع كل تبديل كمثال فردي للمشكلة. وبالتالي، فإن متوسط الحد الأدنى الذي نبحث عنه يتم حسابه على مستوى جميع الحالات الفردية.
n log n الحد الأقصى لعدد المقارنات لمصفوفة حجمها على شكل 2k
كذلك، في حال كان هناك عدة عناصر بنفس القيمة، فإنه لا يوجد تفسير إحصائي واضح لمصطلح «الحالة المتوسطة»، وبالتالي لا يمكن إسقاط النظرية السابقة على جميع الحالات دون وضع افتراضات محددة حول توزيع العناصر وقيمها.
else if leftb ≠ rightb
return compare(leftb, rightb)
البدائل
وفي هذا السياق، تحتاج بعض مشكلات الترتيب حلاً أسرع من من الوقت الذي تحتاجه خوازرميات الترتيب بالمقارنة باستخدام خوارزمية ترتيب؛ مثال على ذلك هو ترتيب الأعداد الصحيحة، حيث تكون جميع العناصر قيما صحيحة. عندما يكون مدى قيم العناصر صغيرًا (مقارنةً بـ عدد العناصر )، فإن الترتيب بالعد هو مثال لخوارزمية تعمل في وقت خطي. لا تعدّ خوارزميات ترتيب الأعداد الصحيحة الأخرى، مثل ترتيب الجذر، أسرع بشكل مقارب من الترتيب بالمقارنة، ولكن من الممكن أن تكون أسرع عمليا.
في هذا الإطار، إن مشكلة فرز أزواج الأرقام غير خاضعة للحد الأدنى (التربيع في n2 ناتج عن عملية بناء الأزواج)؛ الخوارزمية الأكثر شيوعا تحتاج إلى وقت تشغيل ، فقط من المقارنات.
مثال على خوارزمية لإقتران مقارنة
وفي هذا السياق، function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc))
أمثلة
- القائمة التالية تتضمن بعض أنواع المقارنة الأكثر شهرة:
- الترتيب السريع
- ترتيب الكومة
- ترتيب القذائف
- ترتيب الدمج
- ترتيب المقدمة
- ترتيب الإدراج
- ترتيب الإختيار
- ترتيب الفقاعة
- ترتيب الفردي الزوجي
- ترتيب كوكتيل شاكر
- ترتيب الدورة
- ترتيب الفرز والإدماج
- ترتيب سلس
- ترتيب تيم
- ترتيب الكتلة
فرز قائمة مرتبة مسبقًا
ملحوظات
كذلك، إذا كانت القائمة مرتبة نسبيا، فإنه يمكن أن يكون عدد المقارنات المطلوبة لترتيبها أقل بحسب بعض مقاييس الترتيب. تمتاز خوارزمية الترتيب التكيفي بهذه الخاصية؛ خاصية «الترتيب المسبق»، وتعمل بسرعة أكبر على المدخلات شبه المرتبة، غالبًا مع بقاء حاجتها إلى من الوقت في أسوأ حالة. مثال على ذلك خوارزمية ترتيب الكومة التكيفي، وهي خوارزمية ترتيب تعتمد على الأشجار الديكارتية. تحتاج إلى من الوقت، حيث أن هو المتوسط (على كل القيم في التسلسل) لعدد المرات التي يقفز فيها التسلسل من أقل من إلى أكبر من أو العكس.
أو بشكل مكافئ
نحصل على:
بالنظر إلى أول من عوامل (!)
وفي هذا الصدد، إن تحديد العدد الفعلي للمقارنات اللازمة لترتيب عدد معين من العناصر هي مشكلة حسابية صعبة حتى بالنسبة لـعدد قليل من العناصر n، ولا توجد صيغة رياضية بسيطة معروفة للحل. للإطلاع على بعض القيم التي تم حسابها، انظر إلى OEIS:A036604.
في هذا الإطار، حد أعلى مطابق للحد الأدنى أعلاه يأتي من وجود الخوارزميات التي تحقق هذا الحد في أسوأ الحالات، مثل خوارزميتي ترتيب الدمج وترتيب الكومة. النقاش أعلاه يعطي حدًا أدنى مطلقًا، وليس فقط حدًا مقاربًا، لعدد المقارنات، تحديدا من المقارنات. هذا الحد الأدنى جيد إلى حد مقبول (يمكن الوصول إليه بتفاوت خطي من خلال خوارزمية ترتيب الدمج)، ولكن من المعروف أنه غير دقيق. فمثلا،
ومن ناحية أخرى، علما بأنه أقل عدد مثبت من المقارنات لترتيب 13 عنصرًا هو 34 عملية مقارنة.
علاوةً على ذلك، هذا يؤدي إلى جزئية الحد الأدنى من الفرضية. يمكن إعطاء حد أفضل من خلال تقريب ستيرلنغ.
عدد المقارنات المطلوبة لترتيب عناصر قائمة
كذلك، يجب أن تحصل خوارزمية الترتيب على معلومات كافية من عمليات المقارنات لتحديد البديل الصحيح. إذا كانت الخوارزمية تنهي عملها دائمًا بعد من الخطوات على الأكثر، فإنه لا يمكن لها تمييز أكثر من من الحالات لأن العناصر جميعها مميزة ولأن كل مقارنة لها نتيجتين محتملتين فقط. وبالتالي:
كذلك، مثال: لو كان هناك قائمة مكونة من ثلاثة عناصر 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}.
من جهة ثانية، مثال: إذا كانت n=10 , فإن الحد الأدنى يساوي 22, والحد الأدنى الفعلي يساوي كذلك 22, بينما باستخدام تقريب ستيرلينغ، فإن الحد الأدنى (مقرّب باستخدام المعادلة) يساوي 19.عدد المقارنات التي تتطلبها خوارزميات الترتيب بالمقارنة تزداد بالتناسب مع ، حيث أن هو عدد العناصر المطلوب ترتيبها. هذا الحد هو حد محكم بشكل مقارب.
وفي هذا السياق، إذا كان لدينا مجموعة من الأعداد المختلفة (يمكننا افتراض هذا الإختلاف لأن هذا الإختلاف هو تحليل لأسوأ حالة)، فهناك عدد من البدائل يساوي مضروب حجم القائمة (!)، واحد منها فقط يمثل القائمة بالترتيب المطلوب.
حدود الكفاءة ومزايا طرق الترتيب المختلفة
من جانب آخر، هناك حدود هامة لكفاءة خوارزميات الترتيب بالمقارنة. يجب أن يكون متوسط الحد الأدنى للوقت الذي تحتاجه خوارزميات الترتيب بالمقارنة هو Ω(n log n) عدد من عمليات المقارنات، والذي يُعرف باسم الوقت الخطي. هذا الحد الأدنى هو نتيجة لمحدوية المعلومات المتاحة من خلال عملية المقارنات لوحدها، أو بعبارة أخرى، بسبب الهيكل الجبري الغامض للمجموعات المرتبة بالكامل. وبهذا السياق، فإن طرق ترتيب الدمج، وترتيب الكومة، وترتيب المقدمة هي الطرق الأمثل بشكل مقارب من حيث عدد المقارنات التي يجب القيام بها، على الرغم من أن هذا المعيار يهمل العمليات الأخرى عدا المقارنات.
في هذا الإطار، قد تحتاج المقاييس الواقعية لقياس سرعة خوارزمية الترتيب إلى الأخذ بعين الإعتبار قدرة بعض الخوارزميات على الإستخدام الأمثل لذاكرة الحاسب المخزنة مؤقتًا والسريعة نسبيا، أو قد تستفيد بعض التطبيقات من طرق الترتيب حيث تبدأ البيانات المرتبة في الظهور للمستعمل بسرعة (حيث تكون سرعة المستعمل في القراءة عاملا محددا) على العكس من طرق الترتيب التي لا تكون فيها المخرجات متاحة حتى تتم عملية ترتيب القائمة بالكامل.
وعلى صعيد آخر، خوارزميات الترتيب الأخرى التي لا تعتمد على المقارنات (كالأمثلة أدناه) يمكن تشغيلها بكفائة تصل إلى O(n) باستخدام عمليات أخرى غير عملية المقارنة، مما يسمح لها بتجنب الحد الأدنى لخوارزميات الترتيب بالمقارنة (على فرض أن العناصر المراد ترتيبها ثابتة الحجم).
وعلى صعيد آخر، قد تعمل بعض خوارزميات الترتيب بالمقارنة بشكل أسرع في بعض القوائم؛ تحتاج الكثير من خوارزميات الترتيب التكيفي مثل خوارزمية ترتيب الإدراج للتشغيل إلى O(n) من الوقت لترتيب مجموعة من العناصر في قائمة مرتبة بشكل كامل أو شبه مرتبة. وينطبق الحد الأدنى Ω(n log n) فقط على الحالة التي تكون فيها عناصر القائمة بأي ترتيب عشوائي.
وفي السياق ذاته، على الرغم من هذه المحددات، فإن لخوارزميات الترتيب بالمقارنة ميزة عملية ملحوظة وهي أن التحكم في اقتران المقارنة يسمح بالقيام بترتيب الكثير من أنواع البيانات المختلفة والتحكم الدقيق في كيفية القيام بعملية الترتيب لعناصر القائمة. مثلًا، عكس نتيجة اقتران المقارنة يؤدي ال ترتيب عناصر القائمة بشكل عكسي؛ ويمكن كذلك للمستعمل أن يرتب قائمة تتكون من عدد من المجموعات بترتيب معجمي فقط من خلال إنشاء إقتران مقارنة يقوم بمقارنة كل جزء من هذه المجموعات بالتسلسل:
else
ومن ناحية أخرى، يسمح نظام العدّ الثلاثي المتوازن بإجراء مقارنات في خطوة واحدة فقط، تكون نتيجتها واحدة من ثلاث خيارات: «أقل من» أو «أكبر من» أو «يساوي».
return compare(leftc, rightc)
من جانب آخر، خوارزميات الترتيب بالمقارنة تعمل عمومًا بسهولة مع أي نوع من أنواع المجموعات المعقدة مثل ترتيب الأعداد العشرية. علاوةً على ذلك، بمجرد كتابة إقتران مقارنة، يمكن استخدام أي نوع من خوارزميات الترتيب بالمقارنة دون الحاجة للقيام بالتعديلات؛ فيما تتطلب عادة خوارزميات الترتيب التي لا تعتمد على المقارنات اقترانات ترتيب خاصة لكل نوع من البيانات. أدّت هذه المرونة في خوارزميات الترتيب بالمقارنة، إلى جانب كفاءتها على أجهزة الحاسب الحديثة، إلى تفضيل واسع النطاق لخوارزميات الترتيب بالمقارنة في أغلب الحلول العملية.
if lefta ≠ righta
return compare(lefta, righta)
=== ===
- On = 8*n - 1 * (2^8 - 1) / (2 - 1)
- On = 8*n - (n - 1)
- 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
وعلى صعيد آخر، 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 = (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)
- (3) = = // سبع مقارنات على الأكثر مكررة لدمج 4 صفوف بحجم 2
- (4) // خمس عشر مقارنة على الأكثر مكررة مرة واحدة لدمج صفيين بحجم 4
- الصيغة المستخرجة:
- n = 256 = 2^8 (للتبسيط نمثل حجم المصفوفة ل شكل 2^k)
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟