[Powered by Google Translate] [بلبلا ترتیب دیں] [جیکسن STEINKAMP ہارورڈ یونیورسٹی] اس [CS50 ہے. CS50TV] بلبلا ترتیب دیں چھںٹائی الگورتھم کی ایک مثال ہے - ایسا ہے، عناصر کا ایک سیٹ میں حل کرنے کے لئے ایک طریقہ کار صعودی یا نزولی ترتیب. مثال کے طور پر، اگر آپ کو ایک صف ترتیب کرنا چاہتے تھے کی تعداد پر مشتمل [3، 5، 2، 9]، بلبلا کی ترتیب کا صحیح عمل درآمد لوٹ آئیں گے کے مطابق [2، 3، 5، 9] صف صعودی میں. اب، میں pseudocode میں کی وضاحت کرنے جا رہا ہوں کس طرح الگورتھم کام کرتا ہے. 

چلو کا کہنا ہے کہ ہم 5 integers کی ایک فہرست چھانٹ رہا ہے - 3، 2، 9، 6، اور 5. الگورتھم پہلے دو عناصر، 3 اور 2 میں دیکھ کر شروع ہوتا ہے، جانچ پڑتال اور اگر وہ ایک دوسرے کے رشتہ دار آرڈر سے باہر ہو گیا. وہ ہیں - 3 2 سے بڑا ہے. آروہی ترتیب میں، وہ دوسرے کے ارد گرد راستہ ہونا چاہئے. تو، ہم ان سے تبادلہ. [2، 3، 9، 6، 5]: اب فہرست اس طرح لگ رہا ہے. 

اگلا، ہم نے دوسری اور تیسری عناصر، 3 اور 9 میں نظر آتے ہیں. انہوں نے ایک دوسرے کے رشتہ دار صحیح حکم میں ہیں. 3 یہ ہے، تو 9 سے کم الگورتھم ان تبادلہ نہیں ہوتا. اگلا، ہم نے 9 اور 6 بجے لگ رہی ہو. انہوں نے حکم سے باہر ہو گیا. 

تو، ہم ان کی وجہ 9 6 سے بڑھ کر ہے پر تبادلہ کرنے کی ضرورت ہے. آخر میں، ہم نے گزشتہ دو integers، 9 اور 5 میں نظر آتے ہیں. وہ حکم سے باہر ہو، تو وہ تبدیل ہونا چاہئے. فہرست کے ذریعے پہلے مکمل پاس کرنے کے بعد، [2، 3، 6، 5، 9]: یہ اس طرح لگ رہا ہے. برا نہیں ہے. یہ تقریبا کے مطابق ہے. لیکن ہم فہرست کے ذریعے دوبارہ چلانے کے اسے مکمل طور پر حل کرنے کی ضرورت ہے. دو 3 سے کم ہے، تو ہم ان سے تبادلہ نہیں کرتے. 

تین 6 سے کم ہے، تو ہم ان سے تبادلہ نہیں کرتے. چھ 5 سے زیادہ ہے. ہم تبدیل. چھ 9 سے کم ہے. ہم نہیں تبادلہ ہے. دوسرے سے گزرنے کے بعد، یہ اس طرح لگ رہا ہے: [2، 3، 5، 6، 9]. ٹھیک ہے. اب، لکھنے pseudocode میں. بنیادی طور پر، فہرست میں ہر عنصر کے لئے، ہم اس کو دیکھنے کے لئے کی ضرورت ہے اور براہ راست اس کے حق کے عنصر. اگر وہ حکم سے باہر ایک دوسرے کے رشتہ دار ہیں - یہ ہے کہ، اگر بائیں عناصر دائیں جانب ایک سے زیادہ ہے - ہم دو عناصر تبادلہ کرنا چاہئے. 

ہم نے فہرست کے ہر عنصر کے لئے ایسا کرتے ہیں، اور ہم اس کے ذریعے ایک پاس کر دیا ہے. اب ہم صرف پاس کے ذریعے کافی وقت کی فہرست کو یقینی بنانے کے لئے کرنا ہے مکمل طور پر ہے، کے مطابق مناسب طریقے سے ہے. لیکن ہم نے کتنی بار کی فہرست کے ذریعے منتقل کی ہے اس بات کی ضمانت ہے کہ ہم کیا کر رہے ہیں؟ ٹھیک ہے، بدترین حالات کی صورت یہ ہے اگر ہم ایک مکمل طور پر پیچھے کی طرف کی فہرست ہے. اس وقت یہ throughs کے پاس کی ایک بڑی تعداد میں تعداد کے برابر لگتا ہے 1 (ن) کے عناصر کے. اگر اس کا کوئی مطلب نہیں ہے intuitively، ایک سادہ کیس کے بارے میں سوچ - فہرست [2، 1]. 

یہ درست طریقے سے ترتیب کے لئے ایک پاس کے ذریعے لے جا رہا ہے. [3، 2، 1] - سب سے بری حالت ہے کہ 3 عناصر کے ساتھ پیچھے کی طرف کے مطابق، اس طرح 2 تکرار لے جا رہا ہے. ایک iteration کے بعد [2، 1، 3] ہے. دوسری پیداوار کے مطابق صف [1، 2، 3]. تو آپ کو معلوم ہے کہ تم عام طور پر صف کے ذریعے جانے کے لئے نہیں،، ن 1 بار جہاں N صف میں عناصر کی تعداد ہے کے مقابلے میں زیادہ ہے. یہ بلبلا ترتیب دیں کہا جاتا ہے کیونکہ سب سے بڑا عناصر 'بلبلا اپ کرتے ہیں بہت تیزی سے حق کو. اصل میں، یہ الگورتھم بہت دلچسپ رویہ ہے. 

پوری صف کے ذریعے میٹر تکرار کے بعد، rightmost م عناصر کی ضمانت دی ہیں ان کی صحیح جگہ میں حل کیا جائے گا. اگر آپ کو خود کے لئے یہ دیکھنا چاہتے ہیں، ہم اسے ایک مکمل طور پر پیچھے کی طرف [9، 6، 5، 3، 2] فہرست میں کوشش کر سکتے ہیں. ، کی مکمل فہرست کے ذریعے ایک پاس کے بعد، [لکھنے کی آواز] [6، 9، 5، 3، 2،]، [6، 5، 9، 3 2،]، [6، 5، 3، 9 2،]، [6، 5، 3، 2، 9] rightmost 9 عنصر اس کی مناسب جگہ ہے. پاس کے ذریعے دوسرے کے بعد، 6 ہے 'bubbled اپ' دوسری rightmost جگہ. 6 - 9 - حق دونوں عناصر کو ان کی صحیح جگہوں میں ہو جائے گا پہلے دو پاس throughs کے بعد. 

تو، یہ ہم کس طرح الگورتھم کو بہتر بنانے کے لئے استعمال کر سکتے ہیں؟ ٹھیک ہے، صف کے ذریعے ایک iteration کے بعد ہم rightmost عنصر چیک کرنے کے لیے اصل میں ضرورت نہیں ہے کیونکہ ہم جانتے ہیں کے مطابق ہے. دو تکرار کے بعد، ہم اس بات کا یقین کر لیں کہ rightmost دو عناصر جگہ میں ہیں کے لئے جانتے ہیں. لہذا، عام طور پر، مکمل صف کے ذریعے K تکرار کے بعد آخری K عناصر پرکھنے کے بے کار ہے کیونکہ ہم جانتے ہیں وہ پہلے ہی صحیح جگہ میں ہیں. 

تو اگر آپ کو (ن) کے عناصر کا ایک صف چھںٹائی کر رہے ہیں، پہلے iteration - you'll عناصر کے سب الگ الگ ہے - پہلے ن 0. دوسری iteration پر، آپ کو عناصر کے سب لیکن گزشتہ کی طرف دیکھنے کی ضرورت ہوگی - پہلے این 1. ایک اور اصلاح کی اگر فہرست پہلے ہی کے مطابق ہے چیک کرنے کے لیے ہو سکتا ہے ہر iteration کے بعد. اگر یہ پہلے سے ہی حل ہے، ہم زیادہ تکرار کرنے کی ضرورت نہیں ہے فہرست کے ذریعے. ہم یہ کیسے کر سکتے ہیں؟ ٹھیک ہے، اگر ہم ایک فہرست کے پاس کے ذریعے کسی بھی سویپ نہیں ہے یہ واضح ہے کہ فہرست میں پہلے ہی کے مطابق کیا گیا تھا کیونکہ ہم کچھ بھی تبادلہ نہیں کیا. تو ہم ضرور دوبارہ ترتیب کی ضرورت نہیں ہے. 

شاید آپ کو ایک پرچم کہا جاتا ہے 'کے مطابق نہیں متغیر ابتدا کر سکتا ہے اور درست کرنے کے لئے اسے تبدیل جھوٹے اگر آپ پر کسی بھی عناصر کا تبادلہ ہے صف کے ذریعے ایک iteration. یا اسی طرح، ایک انسداد شمار کتنے سویپ تم کسی بھی iteration پر. iteration کے آخر میں، اگر آپ عناصر کا کوئی تبادلہ نہیں کیا، تم جانتے ہو کی فہرست پہلے ہی حل ہے اور تم نے کیا کیا کر رہے ہیں. بلبلا ترتیب دیں، دیگر چھنٹائی یلگوردمز کی طرح ہو، کر سکتے ہیں کسی بھی عناصر ہیں جو ایک آرڈر کا طریقہ ہے کے لئے کام کرنے tweaked. 

یہ دو عناصر دیا ہے آپ کو ایک کہنے کا ایک طریقہ ہے، اگر پہلے ایک سے، یا اس کے برابر دوسرے سے کم زیادہ ہے. مثال کے طور پر، آپ کہہ رہی کی طرف سے حروف تہجی کے حروف ترتیب کر سکتے ہیں کہ ایک <B، B <C وغیرہ، یا آپ کو ہفتے کے دنوں میں الگ الگ جہاں اتوار کو پیر کے روز سے بھی کم ہے جو منگل کے روز سے بھی کم ہے. 

بلبلا ترتیب دیں کی طرف سے کوئی ایک بہت ہی موثر یا فاسٹ چھنٹائی الگورتھم کا مطلب ہے کہ. اس رن ٹائم بدترین بگ این اے ² کیونکہ آپ ایک فہرست کے ذریعے (ن) کے تکرار کرنے کی ہے تمام این عناصر کی جانچ پڑتال ہر پاس کے ذریعے، nxn ن = ². یہ چلت وقت کا مطلب یہ ہے کہ آپ کے عناصر کی تعداد کے طور پر اضافہ چھںٹائی کر رہے ہیں، چلت وقت quadratically بڑھ جاتا ہے. 

لیکن اگر آپ کے پروگرام کی کارکردگی ایک بڑا مسئلہ نہیں ہے یا اگر آپ صرف عناصر کی ایک چھوٹی سی تعداد میں چھانٹ رہا ہے کر رہے ہیں، آپ ببل ترتیب دیں مفید ہو سکتا ہے کیونکہ یہ آسان چھانٹ رہا ہے الگورتھم میں سے ایک ہے سمجھنے کی کوڈ اور. یہ بھی ایک عظیم نظریاتی ترجمہ کے ساتھ تجربہ حاصل کرنے کا ایک طریقہ ہے اصل کام کاج کے کوڈ میں الگورتھم ہے. ٹھیک ہے، یہ آپ کے لئے بلبلا ترتیب دیں. دیکھ کے لئے شکریہ. CS50.TV