بوگو ترتیب
کمپیوٹر سائنس میں [1](اسے [2]،سست ترتیب [3][4]، اٹکل ترتیب بندوقی ترتیب اور بندر تر تیب[5] بھی کہاتا ہے) ایک غیر مؤثر ترتیبی الگورتھم ہے۔ جو پیدائش و پڑتال کے اصول پر کام کرتا ہے۔ یہ معلومات کو ترتیب لگانے کا بہت اچھا طریقہ نہیں ہے اس لیے کسی تحقیقی یا تجارتی مقصد کے لیے استعمال نہیں کیا جاتا بلکہ اسے تعلیمی مقاصد کے لیے استعمال کیا جاتا ہے۔ اسے منطقی پروگرامنگ[2][2][4] سکھانے کے لیے بھی استعمال کیا جاتا ہے۔ اگر ہم اس طریقہ سے تاش کے پتوں کو ترتیب لگانا چاہتے ہیں تو پہلے یہ معلوم کریں گے کہ وہ پہلے ہی ترتیب میں ہیں یا نہیں۔ اگر وہ ترتیب میں نہیں ہیں تو ہم پتوں کو ہوا میں اچھالیں گے اور پھر ان بکھرے ہوئے پتوں کو بغیر کسی ترتیب کے اٹھا کر دوبارہ دیکھیں گے کہ وہ ترتیب میں ہیں یا نہیں۔ اگر دوبارہ ترتیب میں نہیں ہیں تو یہ عمل دہرایا جائے گا یہاں تک کہ تمام پتے ترتیب میں آجائیں۔ اس طریقہ ترتیب کا نام انگریزی لفظ بوگس سے مشتق ہے۔
الگوتھم کی وضاحت[ترمیم]
ذیل میں الگورتھم کی وضاحت اور اس کا عمومی کوڈ(سوڈو کوڈ) دیا گیا ہے۔
(while not isInOrder( deck (shuffle (deck
کل وقت اور اختتام[ترمیم]
یہ الگورتھم اپنی فطرت میں احتمالی(probabilistic) ہے۔ ہر ایک عنصر علاحدہ علاحدہ محفوظ کیا جاتا ہے۔ اس لیے اس کی اوسط پیجیدگی میں تقابل کی ممکنہ تعداد!e-1) n) ہے۔ جبکہ اوسط پیجیدگی میں باہمی تبدیلیوں کی ممکنہ تعداد بھی!e-1) n) ہے۔ باہمی تبدیلیوں کی تعداد کا انحصار تقابل کی تعداد پر ہے۔ جیسے جیسے معلومات (تاش کے پتوں کی مثال میں تاش کے پتے معلومات ہیں) کی تعداد بڑھتی جائے گی ویسے ہی تقابل بھی بڑھتے جائیں گے۔ بدترین پیجیدگی کی صورت میں تقابل اور باہمی تبدیلیاں دونوں ہی قابو سے باہر ہوجائیں گی اور ان کی تعداد لامحدود بھی ہو سکتی ہے۔ بہترین پیجیدگی کی صورت اس وقت پیدا ہوتی ہے جب معلومات پہلے ہی ترتیب میں ہوں اور انھیں دوبارہ ترتیب لگانے کی ضرورت نہ ہو۔ اس صورت میں تقابل کی تعداد1 - n ہوگی جبکہ کوئی باہمی تبدیلی نہیں ہوگی۔ یہاں n سے مراد معلومات کی تعداد ہے۔ معلومات کے کسی بھی مجموعہ کی شکل میں الگورتھم کے چلنے کا وقت محدود ہو سکتا ہے لیکن اس کے لیے بن مانس کا لا محدود کھیل کا نظریہ عمل کرے گا کہ معلومات کی محدود وقت میں درست ترتیب ممکن ہو سکتی ہے۔
متعلقہ الگورتھم[ترمیم]
گورو ترتیب یہ الگورتھم 2011 میں گوگل کوڈ جیم[4] میں پیش کیا گیا تھا۔ اگر دی گئی معلومات ترتیب میں نہ ہوں تو دی گئی معلومات کا ایک اٹکل (random) تحتی سیٹ لے کر اس پر ترتیب لگائی جاتی ہے۔ اگر ہر بار درست تحتی سیٹ لیا جائے تو ممکن ہے کہ معلومات مناسب وقت میں ترتیب سے لگ جائیں۔ بوگو بوگو ترتیب یہ ترتیبی الگورتھم قیامت تک معلومات کو ترتیب لگاتا رہے گا۔ اس کے کام کرنے کا طریقہ بوگو ترتیب کی طرح ہے۔ اس الگورتھم کے مطابق دی گئی فہرست میں اگر پہلے دو عناصر اگر ترتیب میں نہیں ہیں تو ان پر بوگو ترتیب لاگو کی جائے گی۔ جب دونوں عناصر ترتیب میں آجائیں گے تب تیسرے کو شامل کیا جائے گا۔ اگر تینوں ترتیب میں نہیں ہیں تو تینوں کو ترتیب میں لانے کے لیے پھر بوگو ترتیب لگائی جائے گی اور اس طرح ہر مرتبہ ترتیب لگانے کے بعد اگلا عنصر شامل کیا جائے گا اور پھر بوگو ترتیب لگائے جائے گی۔ یہ ترتیب بوگو ترتیب کے مقابلے میں بہت ہی زیادہ پیچیدہ ہے کیونکہ ہر مرتبہ اس کے بے ترتیب ہونے کا اندیشہ بڑھتا چلائے گا۔ بوزو ترتیب یہ بھی ایک اٹکل(random) ترتیبی الگورتھم ہے۔ اس الگورتھم کے مطابق دی گئی ترتیب میں سے کوئی بھی دو عدد چن لیے جائیں گے۔ اور ان کی جگہیں آپس میں تبدیل کردی جائیں گی۔ پھر دیکھا جائے گا کہ کیا فہرست ترتیب میں ہے۔ اگر فہرست ترتیب میں نہیں ہے تو دوبارہ کوئی سے دو عدد لیے جائیں گے اور ان کی جگہ تبدیل کرکے فہرست کی ترتیب کی پڑتال کی جائے گی۔ اور اس طرح یہ سلسلہ چلتا رہے گا جب تک کہ ہمیں درست ترتیب نہ مل جائے۔ دیکھنے میں یہ ترتیب بھی بہت ہی پیچیدہ ہے کیونکہ اس میں ممکن ہے کہ ہماری فہرست پہلے ہی ترتیب میں ہو اور ہم اسے خراب کر لیں لیکن ایچ گربر کے تجزئے کے مطابق بعض اوقات یہ ترتیب شاندار نتائج بھی دے سکتی ہے اور اس کی اوسط پیجیدگی!n ہے۔ کوانٹم بوگو ترتیب کوانٹم بوگو ترتیب کمپیوٹر کے سائنس دانوں میں ایک لطیفے کے طور پر مشہور ہے۔ اس کے مطابق ایک کوانٹم کمپیوٹر اٹکل کی مدد سے فہرست مرتب کرے گا۔ پھر اس فہرست کے ویو فنکشن کی!n شاخیں بنائے گا۔ پھر ایک ہی مرتبہ پھینٹنے سے ہمارے پاس ترتیب شدہ فہرست آجائے گی۔
حوالہ جات[ترمیم]
- ↑ 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 4475, Springer-Verlag, pp. 183–197, doi:10.1007/978-3-540-72914-3_17.
- ^ ا ب پ 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, pp. 192–203, doi:10.1145/1086365.1086390
- ↑ Naish, Lee (1986), "Negation and quantifiers in NU-Prolog", Proceedings of the Third International Conference on Logic Programming, Lecture Notes in Computer Science 225, Springer-Verlag, pp. 624–634, doi:10.1007/3-540-16492-8_111.
- ^ ا ب پ Naish, Lee (June 1995), Pruning in logic programming, Tech. Report 95/16, Melbourne, Australia: Department of Computer Science, University of Melbourne, CiteSeerX: 10.1.1.54.2347.
- ↑ Princeton University: https://www.princeton.edu/~achaney/tmve/wiki100k/docs/Bogosort.html آرکائیو شدہ (Date missing) بذریعہ princeton.edu (Error: unknown archive URL)