ترتيب غبي

من ويكيبيديا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
ترتيب غبي
Bogo sort animation.gif
بيانات عامّة
الصنف
بنية البيانات
الأداء
أسوء حالة

غير معروف (النوع الشوائي)

O((n+1)!) (النوع الحتمي)
الحالة المُثلى
O(n)[1]
الأداء الوسطي
O((n+1)!)[1]
أسوأ حالة تعقيد مكاني
[2] عدل القيمة على Wikidata

في علم الحاسوب ، bogosort [3] [4] (المعروفة أيضًا باسم الترتيب التبادلي ، الترتيب الغبي، الترتيب الأحمق، [5] أو الترتيب البطيء [6] ) هي عبارة عن خوارزمية ترتيب تعتمد على مبدأ التجربة والخطأ. تقوم الخوارزمية بإنشاء تباديل مختلفة عشوائياً للمُدخلات حتى تجد تبديل للمُدخلات تكون فيه جميع العناصر مرتبة. لا تعتبر الخوارزمية مفيدة بشكل عملي للترتيب نظرا للوقت الهائل التي تستغرقه ، ولكن يمكن استخدامها للأغراض التعليمية ، أو للمقارنه بخوارزميات أكثر كفاءة.

هنالك نوعان من هذه الخوارزمية: نسخة حتمية تقوم بتجربة كل التباديل الممكنة للمُدخلات حتى تصل إلى التبديل المرتب ، [7] [6] ونسخة عشوائية تبدل مُدخلاتها بشكل عشوائي. تشبيه عملي للنوع الثاني هو محاولة ترتيب مجموعة أوراق اللعب عن طريق رمي المجموعة في الهواء ، جمع البطاقات من الأرض عشوائيًا، وتكرار العملية حتى يتم الحصول على مجموعة مرتبة. اسمها باللغة الإنجليزية هو عبارة من الكلمتين الأحمق (bogus) والفرز (sort) . [8]

انظر أيضًا[عدل]

مراجع[عدل]

  1. أ ب Gruber, H.؛ Holzer, M.؛ Ruepp, O.، "Sorting the slow way: an analysis of perversely awful randomized sorting algorithms"، 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007 (PDF)، Lecture Notes in Computer Science، Springer-Verlag، ج. 4475، ص. 183–197، doi:10.1007/978-3-540-72914-3_17.
  2. ^ "Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting AlgorithmsFun with Algorithms: 4th International Conference, FUN 2007, Castiglioncello, Italy, June 3-5, 2007. Proceedings: 183–197، 2007، doi:10.1007/978-3-540-72914-3_17. {{استشهاد بدورية محكمة}}: تحقق من التاريخ في: |date= (مساعدة)
  3. ^ Gruber, H.؛ Holzer, M.؛ Ruepp, O.، "Sorting the slow way: an analysis of perversely awful randomized sorting algorithms"، 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007 (PDF)، Lecture Notes in Computer Science، Springer-Verlag، ج. 4475، ص. 183–197، doi:10.1007/978-3-540-72914-3_17.
  4. ^ Kiselyov, Oleg؛ Shan, Chung-chieh؛ Friedman, Daniel P.؛ Sabry, Amr (2005)، "Backtracking, interleaving, and terminating monad transformers: (functional pearl)"، Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05) (PDF)، SIGPLAN Notices، ص. 192–203، doi:10.1145/1086365.1086390، مؤرشف من الأصل (PDF) في 26 مارس 2012، اطلع عليه بتاريخ 22 يونيو 2011
  5. ^ E. S. Raymond. "bogo-sort". The New Hacker’s Dictionary. MIT Press, 1996.
  6. أ ب Naish, Lee (1986)، "Negation and quantifiers in NU-Prolog"، Proceedings of the Third International Conference on Logic Programming، Lecture Notes in Computer Science، Springer-Verlag، ج. 225، ص. 624–634، doi:10.1007/3-540-16492-8_111.
  7. ^ Kiselyov, Oleg؛ Shan, Chung-chieh؛ Friedman, Daniel P.؛ Sabry, Amr (2005)، "Backtracking, interleaving, and terminating monad transformers: (functional pearl)"، Proceedings of the Tenth ACM SIGPLAN International Conference on Functional Programming (ICFP '05) (PDF)، SIGPLAN Notices، ص. 192–203، doi:10.1145/1086365.1086390، مؤرشف من الأصل (PDF) في 26 مارس 2012، اطلع عليه بتاريخ 22 يونيو 2011
  8. ^ "bogosort"، xlinux.nist.gov، مؤرشف من الأصل في 8 فبراير 2022، اطلع عليه بتاريخ 11 نوفمبر 2020.