بوغوسورت

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
📷 يحتوي على 31 صور
الموسوعة الحرة

في علوم الحاسوب ، تُعدّ خوارزمية بوغوسورت [ 1 ] [ 2 ] (المعروفة أيضًا باسم فرز التبديلات وفرز الغبي [ 3 ] ) خوارزمية فرز تعتمد على نموذج التوليد والاختبار . تقوم هذه الخوارزمية بتوليد تباديل متتالية لمدخلاتها حتى تجد تبديلاً مُرتبًا. لا تُعتبر هذه الخوارزمية مفيدة للفرز، ولكن يمكن استخدامها لأغراض تعليمية، لمقارنتها بخوارزميات أكثر كفاءة. اسم الخوارزمية مُشتق من كلمتي "بوغوس" و "فرز" . [ 4 ]

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

التحليل الاحتمالي

على الرغم من أن خوارزمية Bogosort تُناقش في المقام الأول كمثال تعليمي لخوارزمية فرز غير فعالة، إلا أنه يمكن ربطها أيضًا بنظرية الاحتمالات الأساسية .

إحدى طرق تحليل سلوكها المتوقع هي النظر في احتمالية الحصول على تسلسل مُرتب بعد عمليات خلط عشوائية متكررة. وهذا يُشابه الصيغة العامة لاحتمالية تحقيق نجاح واحد على الأقل في سلسلة من المحاولات المستقلة.

P(نجاح واحد على الأقل)=1-(P(الفشل في إحدى المحاولات))ن{\displaystyle P({\text{نجاح واحد على الأقل}})=1-(P({\text{فشل في محاولة واحدة}}))^{n}}

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

P(مصنفة ضمن ك خلط)=1-(1-1ن!)ك{\displaystyle P({\text{sorted within }}k{\text{ shuffles}})=1-\left(1-{\tfrac {1}{n!}}\right)^{k}}

يُبرز هذا الإطار عدم كفاءة بوغوسورت الشديدة: حتى بالنسبة للقيم المتواضعة لـن{\displaystyle n}يبقى احتمال النجاح ضئيلاً للغاية ما لمك{\displaystyle k}كبير بشكل فلكي . [ 6 ] [ 7 ]

وصف الخوارزمية

الشفرة الزائفة

فيما يلي وصف للخوارزمية العشوائية بلغة شبه رمزية :

دالة bogoSort(deck: List ): بينما لم يتم فرز قائمة deck : خلط (مجموعة الأوراق)

ج

تطبيق بلغة C :

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <stdbool.h> #include <stddef.h>دالة shuffle ( int a [], int length ) { int temp ; int random ;for ( size_t i = 0 ; i < length ; i ++ ) { random = rand () % length ; temp = a [ random ]; a [ random ] = a [ i ]; a [ i ] = temp ; } }دالة منطقية sorted ( مصفوفة من الأعداد الصحيحة a ، طول المصفوفة من الأعداد الصحيحة length ) { for ( size_t i = 0 ; i < length - 1 ; i ++ ) { if ( a [ i ] > a [ i + 1 ]) { return false ; } } return true ; }void bogoSort ( int a [], int length ) { while ( ! sorted ( a , length )) { shuffle ( a , length ); } }int main ( void ) { int input [] = { 68 , 14 , 78 , 98 , 67 , 89 , 45 , 90 , 87 , 78 , 65 , 74 }; int size = sizeof ( input ) / sizeof ( input [ 0 ] );srand (( unsigned ) time ( NULL ));bogoSort ( input , size );printf ( "النتيجة المرتبة:" ); for ( size_t i = 0 ; i < size ; i ++ ) { printf ( "%d" , input [ i ]); } printf ( " \n " );return 0 ; }

بايثون

تطبيق بلغة بايثون :

استيراد عشوائي# تتحقق هذه الدالة مما إذا كانت المصفوفة مرتبة أم لا. def is_sorted ( a : list [ int ]) -> bool : for i in range ( 1 , len ( a )): if a [ i ] < a [ i - 1 ]: return False return True# تقوم هذه الدالة بخلط عناصر المصفوفة بشكل متكرر حتى يتم ترتيبها. def bogo_sort ( a : list [ int ]) -> list [ int ]: while not is_sorted ( a ): random . shuffle ( a ) return a# تُنشئ هذه الدالة مصفوفة بقيم عددية عشوائية. def generate_random_array ( size : int , min_val : int , max_val : int ) -> list [ int ]: return [ random . randint ( min_val , max_val ) for _ in range ( size )]إذا كان __name__ == "__main__" : # حجم المصفوفة المُولّدة عشوائيًا، وقيمتها الدنيا، وقيمتها القصوى. size : int = 10 min_val : int = 1 max_val : int = 100 random_array : list [ int ] = generate_random_array ( size , min_val , max_val ) print ( "المصفوفة غير المرتبة:" , random_array ) sorted_arr = bogo_sort ( random_array ) print ( "المصفوفة المرتبة:" , sorted_arr )

يُنشئ هذا الكود مصفوفة عشوائية - random_array - في الدالة generate_random_array، والتي سيتم فرزها عن طريق خلطها في الدالة bogosort. جميع البيانات في المصفوفة هي أعداد طبيعية من 1 إلى 100.

مدة التشغيل والإنهاء

وقت التشغيل التجريبي لـ bogosort

إذا كانت جميع العناصر المراد فرزها متميزة، فإن العدد المتوقع للمقارنات التي يتم إجراؤها في الحالة المتوسطة بواسطة خوارزمية فرز بوغو العشوائية يكون مكافئًا تقريبًا لـ(هـ-1)ن!{\displaystyle (e-1)n!}ويبلغ العدد المتوقع لعمليات التبادل في الحالة المتوسطة ما يلي:(ن-1)ن!{\displaystyle (n-1)n!}[ 1 ] يزداد عدد عمليات التبديل المتوقعة أسرع من عدد المقارنات المتوقعة، لأنه إذا لم تكن العناصر مرتبة، فسيتم اكتشاف ذلك عادةً بعد بضع مقارنات فقط، بغض النظر عن عدد العناصر؛ لكن جهد خلط المجموعة يتناسب طرديًا مع حجمها. في أسوأ الأحوال ، يكون عدد المقارنات والتبديلات غير محدود، لنفس السبب الذي يجعل رمي قطعة نقدية قد يُظهر صورةً عدة مرات متتالية.

يتحقق أفضل سيناريو إذا كانت القائمة كما هي مُرتبة بالفعل؛ في هذه الحالة يكون العدد المتوقع للمقارنات هون-1{\displaystyle n-1}ولا يتم إجراء أي عمليات تبادل على الإطلاق. [ 1 ]

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

جوروسورت
خوارزمية طُرحت في مسابقة جوجل للبرمجة عام ٢٠١١. [ ٨ ] طالما أن القائمة غير مرتبة، يتم تبديل مجموعة فرعية من جميع العناصر عشوائيًا. إذا تم اختيار هذه المجموعة الفرعية على النحو الأمثل في كل مرة، فإن القيمة المتوقعة لإجمالي عدد مرات تنفيذ هذه العملية تساوي عدد العناصر التي تم تبديلها. من الناحية التقنية، لا تُعد خوارزمية Gorosort خوارزمية فرز، بل هي خوارزمية لتبديل قائمة من العناصر (مع العلم بترتيبها الأصلي) بحيث تظهر بالترتيب الصحيح.
بوغوبوغوسورت
خوارزمية تستدعي نفسها بشكل متكرر بنسخ أصغر فأصغر من بداية القائمة للتحقق من ترتيبها. الحالة الأساسية هي عنصر واحد، وهو دائمًا مُرتب. في الحالات الأخرى، تُقارن الخوارزمية العنصر الأخير بأكبر عنصر من العناصر السابقة في القائمة. إذا كان العنصر الأخير أكبر من أو يساوي العنصر السابق، تتحقق الخوارزمية مما إذا كان ترتيب النسخة الجديدة مطابقًا للنسخة السابقة، وفي هذه الحالة تُنهي عملها. وإلا، تُعيد الخوارزمية ترتيب النسخة الحالية من القائمة وتُعيد بدء عملية التحقق المتكررة. [ 9 ]
بوزوسورت
خوارزمية فرز أخرى تعتمد على الأرقام العشوائية. إذا لم تكن القائمة مرتبة، فإنها تختار عنصرين عشوائيًا وتبدلهما، ثم تتحقق مما إذا كانت القائمة مرتبة. يُعد تحليل وقت تشغيل خوارزمية bozosort أكثر صعوبة، ولكن توجد بعض التقديرات في تحليل هـ. غروبر لخوارزميات الفرز العشوائي "السيئة للغاية". [ 1 ]يا(ن!){\displaystyle O(n!)}تبين أن هذا هو متوسط ​​الحالة المتوقعة.
أسوأ تصنيف
خوارزمية فرز دنيا مضمونة الإنجاز في وقت محدود؛ ومع ذلك، قد تكون كفاءتها سيئة للغاية، اعتمادًا على تكوينها.أسوأ الأنواع{\displaystyle {\texttt {worstsort}}}تعتمد الخوارزمية على خوارزمية فرز سيئة.بادسورت{\displaystyle {\texttt {badsort}}}تقبل خوارزمية الفرز السيئ معلَمَين:ل{\displaystyle L}وهي القائمة التي سيتم فرزها، وك{\displaystyle k}وهو مستوى التكرار.ك=0{\displaystyle k=0}،بادسورت{\displaystyle {\texttt {badsort}}}يستخدم ببساطة خوارزمية فرز شائعة، مثل فرز الفقاعات ، لفرز مدخلاته وإرجاع القائمة المرتبة. أي بعبارة أخرى،بادسورت(ل،0)=مشروب الفقاعات(ل){\displaystyle {\texttt {badsort}}(L,0)={\texttt {bubblesort}}(L)}لذلك، فإن التعقيد الزمني لخوارزمية badsort هويا(ن2){\displaystyle O(n^{2})}لوك=0{\displaystyle k=0}ومع ذلك، بالنسبة لأيك>0{\displaystyle k>0}،بادسورت(ل،ك){\displaystyle {\texttt {badsort}}(L,k)}يقوم أولاً بإنشاءP{\displaystyle P}، قائمة بجميع تباديلل{\displaystyle L}. ثم،بادسورت{\displaystyle {\texttt {badsort}}}يحسببادسورت(P،ك-1){\displaystyle {\texttt {badsort}}(P,k-1)}، ويعيد العنصر الأول من المجموعة المرتبةP{\displaystyle P}لصنعأسوأ الأنواع{\displaystyle {\texttt {worstsort}}}متشائم للغاية،ك{\displaystyle k}يمكن إسنادها إلى قيمة دالة متزايدة قابلة للحساب مثلو:شمال→شمال{\displaystyle f:\mathbb {N} \to \mathbb {N} }(مثال)و(ن)=أ(ن،ن){\displaystyle f(n)=A(n,n)}، أينأ{\displaystyle A}( دالة أكرمان ). لذلك، لترتيب قائمة بشكل سيئ بشكل عشوائي، سيتم تنفيذأسوأ الأنواع(ل،و)=بادسورت(و(طول(ل))){\displaystyle {\texttt {worstsort}}(L,f)={\texttt {badsort}}(f({\texttt {length}}(L)))}، أينطول(ل){\displaystyle {\texttt {length}}(L)}هو عدد العناصر فيل{\displaystyle L}تتميز الخوارزمية الناتجة بالتعقيدΩ((ن!(و(ن)))2){\textstyle \Omega \left(\left(n!^{(f(n))}\right)^{2}\right)}، أينن!(م)=(...((ن!)!)!...)!{\displaystyle n!^{(m)}=(\dotso ((n!)!)!\dotso )!}= مضروب العددن{\displaystyle n}تكرارم{\displaystyle m}مرات. يمكن جعل هذه الخوارزمية غير فعالة بالقدر الذي يرغب فيه المرء عن طريق اختيار دالة نمو سريعة بما فيه الكفايةو{\displaystyle f}[ 10 ]​
فرز بطيء
خوارزمية فرز فكاهية مختلفة تستخدم استراتيجية فرق تسد مضللة لتحقيق تعقيد هائل.
بوغوسورت الكمي
خوارزمية فرز افتراضية مبنية على خوارزمية بوغوسورت، ابتُكرت على سبيل المزاح بين علماء الحاسوب. تُولّد الخوارزمية تبديلاً عشوائياً لمدخلاتها باستخدام مصدر كمومي للإنتروبيا، وتتحقق مما إذا كانت القائمة مُرتبة، وإذا لم تكن كذلك، فإنها تُدمر الكون. بافتراض صحة تفسير الأكوان المتعددة ، فإن استخدام هذه الخوارزمية سيؤدي إلى وجود كون واحد على الأقل باقٍ حيث تم فرز المدخلات بنجاح.يا(ن){\displaystyle O(n)}الوقت. [ 11 ]

انظر أيضاً

مراجع

  1. 1 2 3 4 5 6 غروبر، هـ.؛ هولزر، م.؛ روب، أ. (2007)، "الفرز بالطريقة البطيئة: تحليل لخوارزميات الفرز العشوائي السيئة بشكل منحرف"، المؤتمر الدولي الرابع حول متعة الخوارزميات، كاستيليونشيلو، إيطاليا، 2007 (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب، المجلد  4475، سبرينغر-فيرلاغ، الصفحات 183-197 ، doi : 10.1007/978-3-540-72914-3_17 ، ISBN  978-3-540-72913-6.
  2. 1 2 كيسليوف، أوليغ؛ شان، تشونغ-تشيه؛ فريدمان، دانيال ب.؛ صبري، عمرو (2005)، "التراجع، والتشابك، وإنهاء محولات الموناد: (لؤلؤة وظيفية)"، وقائع المؤتمر الدولي العاشر لجمعية ACM SIGPLAN حول البرمجة الوظيفية (ICFP '05) (ملف PDF) ، إشعارات SIGPLAN، الصفحات 192-203 ، doi : 10.1145/1086365.1086390 ، S2CID 1435535 ، مؤرشف من الأصل (ملف PDF) في 26 مارس 2012 ، تم استرجاعه في 22 يونيو 2011  
  3. ↑ إي إس ريموند. "فرز بوجو". قاموس المخترق الجديد . مطبعة معهد ماساتشوستس للتكنولوجيا، 1996.
  4. ↑ "bogosort" . xlinux.nist.gov . تم الاطلاع عليه بتاريخ 11 نوفمبر 2020 .
  5. ↑ نايش، لي (1986)، "النفي والمحددات الكمية في NU-Prolog"، وقائع المؤتمر الدولي الثالث حول البرمجة المنطقية ، سلسلة محاضرات في علوم الحاسوب ، المجلد 225، سبرينغر-فيرلاغ، الصفحات 624-634 ، doi : 10.1007/3-540-16492-8_111 ، ISBN   978-3-540-16492-0.
  6. ↑ بوبيت، زاك (5 يناير 2021). "كيفية إيجاد احتمال نجاح واحد على الأقل" . ستاتولوجي . تم الاسترجاع في 6 أكتوبر 2025 .
  7. ↑ ماجور، ليزلي؛ جولدليست، آمي (1 أبريل 2024). "حساب أحداث على الأقل، وعلى الأكثر، وأكثر من 'س'" .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
  8. ↑ مسابقة جوجل كود جام 2011، جولات التأهيل، المسألة د
  9. ↑ بوغوبوغوسورت
  10. ↑ ليرما، ميغيل أ. (2014). "إلى أي مدى يمكن أن تكون خوارزمية الفرز غير فعالة؟". arXiv : 1406.1077 [ cs.DS ].
  11. ↑ ذا أذر تري (23 أكتوبر 2009). "كوانتوم بوغوسورت" (ملف PDF) . ماث نيوز . 111 (3): 13. مؤرشف (ملف PDF) من الأصل في 5 يوليو 2020. تم الاطلاع عليه في 20 مارس 2022 .