>> [موسیقی بجانے]
ڈوگ لایڈ: ٹھیک ہے، تو بلبلا طرح ایک الگورتھم ہے
آپ عناصر کا ایک سیٹ کو حل کرنے کے لئے استعمال کر سکتے ہیں.
چلو اس کا کام کرتا ہے کہ کس طرح پر ایک نظر ڈالیں.
>> تاکہ بنیادی خیال کے پیچھے بلبلا طرح ہے.
ہم عام طور پر زیادہ منتقل کرنے کے لئے چاہتے ہیں عام طور پر درست کرنے کے لئے قابل قدر عناصر،
اور عام طور پر قابل قدر عناصر کم بائیں، ہم توقع کریں گے کے طور پر.
ہم کم چیزوں میں بننا چاہتا ہوں آغاز، اور اعلی چیزوں
آخر میں ہونا.
>> ہم یہ کیسے کرتے ہیں؟
ویسے pseudocode کے کوڈ میں، ہم چلو، کہہ سکتے ہیں
ایک غیر صفر کی قیمت کرنے کے لئے ایک سویپ کاؤنٹر قائم.
ہم ایک دوسرے میں ایسا کیوں ہم دیکھیں گے.
اور پھر ہم نے مندرجہ ذیل کا اعادہ تبدیل کردہ لسٹ انسداد 0 ہے جب تک عمل کو،
یا ہم سب میں کوئی سویپ تک.
>> تبادلہ کاؤنٹر ری سیٹ 0 0 یہ پہلے سے ہی نہیں ہے تو.
پھر ہر نظر عناصر کے ملحقہ جوڑی.
ان دو عناصر ہیں تو نہیں کی ترتیب میں، ان کے تبادلہ،
اور سویپ کاؤنٹر پر 1 کا اضافہ.
آپ کے بارے میں سوچ رہے ہیں اگر آپ اسے دیکھ سے پہلے،
یہ کم منتقل کرے گا کہ محسوس بائیں قدر عناصر
اور اعلی، دائیں عناصر قابل قدر مؤثر طریقے سے ہم کیا کرنا چاہتے ہیں کر رہے ہیں،
جو ان گروپوں منتقل اس طرح میں عناصر کی.
کس طرح اس کو دیکھ دو ہمارے صف کا استعمال کرتے ہوئے نظر ہو سکتا ہے
ہم ٹیسٹ کرنے کے لئے استعمال کیا جاتا ہے ان یلگوردمز.
ہم ایک بار پھر یہاں ایک ناچھانٹا ہوا سرنی ہے عناصر میں سے سب کی طرف سے اس بات کا اشارہ
سرخ رنگ میں کیا جا رہا ہے.
اور مجھے میری تبدیل کردہ کاؤنٹر قائم ایک nonzero قیمت پر.
میں منمانے منتخب کیا منفی 1-- یہ 0 نہیں ہے.
ہم اس عمل دوبارہ کرنا چاہتے ہیں تبدیل کردہ لسٹ کاؤنٹر تک 0.
مجھے میری تبدیل کردہ مقرر یہی وجہ ہے کچھ غیر صفر کی قیمت کے لئے کاؤنٹر،
دوسری صورت میں کیونکہ تبدیل کردہ لسٹ انسداد 0 ہو جائے گا.
ہم بھی شروع نہیں کریں گے الگورتھم کے عمل.
تو ایک بار پھر، اقدامات are-- تبدیل کردہ لسٹ کاؤنٹر ری سیٹ
0، پھر ہر ملحقہ دیکھو جوڑے، اور وہ حکم سے باہر ہیں تو،
ان کا تبادلہ، اور 1 کا اضافہ تبدیل کردہ لسٹ کاؤنٹر پر.
تو اس عمل شروع کرتے ہیں.
تو ہمیں کیا پہلی بات یہ ہے ہم 0 ادلہ کاؤنٹر قائم
اور پھر ہم تلاش شروع ایک ملحقہ جوڑی میں.
>> تو ہم سب سے پہلے 5 اور 2 میں دیکھ کر شروع.
ہم نے باہر ہیں کہ دیکھیں آرڈر اور تو ہم ان سے تبادلہ.
اور ہم تبدیل کردہ لسٹ کاؤنٹر پر 1 کا اضافہ.
تو اب ہماری ادلہ انسداد 1، اور 2 اور 5 تبدیل کر دیا گیا ہے.
اب ہم پھر عمل کو دہرائیں.
>> ہم اگلے ملحقہ جوڑی پر نظر، 5 اور وہ بھی حکم سے باہر ہو 1--،
تو ہم ان کا تبادلہ شامل تبدیل کردہ لسٹ کاؤنٹر پر 1.
پھر ہم 5 اور 3 میں نظر آتے.
وہ حکم سے باہر ہیں، تو ہم تبادلہ ان کے اور ہم تبدیل کردہ لسٹ کاؤنٹر پر 1 کا اضافہ.
پھر ہم 5 اور 6 میں نظر آتے ہیں.
انہوں نے حکم میں ہیں، تو ہم اصل نہیں ہے کچھ اس وقت تبادلہ کرنے کی ضرورت.
پھر ہم 6 اور 4 دیکھو.
وہ حکم سے باہر بھی ہیں، تو ہم تبادلہ ان کے اور ہم تبدیل کردہ لسٹ کاؤنٹر پر 1 کا اضافہ.
>> اب کیا ہوا ہے محسوس.
ہم آخر 6 تمام راستے منتقل کر دیا گیا.
انتخاب کی طرح میں، آپ کو ہے تو اس ویڈیو کو دیکھا، کیا ہم نے کیا تھا
ہم آگے بڑھ رہے ہیں ختم عمارت میں سب سے چھوٹی عناصر
سے بنیادی طور پر کے مطابق صف سب سے بڑا کرنے کے لئے، سب سے چھوٹی بائیں سے دائیں.
بلبلا طرح کی صورت میں، ہم ہیں تو یہ خاص طور پر مندرجہ ذیل الگورتھم،
ہم اصل میں تعمیر کیا جائے گا کے لئے جا رہے دائیں سے مطابق صف
سب سے چھوٹی، سب سے بڑا بائیں.
ہم مؤثر طریقے سے 6، پر bubbled ہے سب سے بڑی قیمت، ختم کرنے کے لئے تمام طریقہ.
>> اور اس طرح ہم اب اعلان کر سکتے ہیں کہ کے مطابق ہے کہ،
اور مستقبل میں iterations-- صف کے ذریعے جانے again--
اب ہم 6 پر غور کرنے کی ضرورت نہیں ہے.
ہم صرف غور کرنا ہوگا ناچھانٹا ہوا عناصر
جب ہم ملحقہ جوڑوں میں تلاش کر رہے ہیں.
تو ہم نے ایک ختم کر دیا ہے بلبلا طرح سے گزرنا.
تو اب ہم سوال پر واپس جانا، تبدیل کردہ لسٹ انسداد 0 ہے جب تک دہرائیں.
ویسے ادلہ کاؤنٹر 4 ہے، تو ہم جا رہے ہیں
پھر اس عمل کو دہرانے رکھنے کے لئے.
>> ہم تبدیل کردہ لسٹ کاؤنٹر ری سیٹ کرنے کے لئے جا رہے ہیں 0، اور ہر ملحقہ جوڑی دیکھو.
تو ہم وہ کر رہے ہیں 1-- 2 کے ساتھ شروع کریں اور حکم سے باہر ہے، تو ہم ان کا تبادلہ
اور ہم تبدیل کردہ لسٹ کاؤنٹر پر 1 کا اضافہ.
2 اور 3، وہ ترتیب میں ہیں.
ہم کچھ بھی کرنے کی ضرورت نہیں ہے.
3 اور 5 کے حکم میں ہیں.
ہم وہاں کچھ بھی کرنے کی ضرورت نہیں ہے.
>> 5 اور 4، وہ باہر ہیں حکم کی، اور ہم
ان کا تبادلہ اور شامل کرنے کی ضرورت تبدیل کردہ لسٹ کاؤنٹر پر 1.
اور اب ہم، 5 منتقل کر دیا گیا اگلے سب سے بڑا عنصر،
ناچھانٹا ہوا حصہ کے اختتام پر.
تو اب ہم اس کال کر سکتے ہیں مطابق حصہ کا حصہ.
>> اب آپ دیکھ رہے ہیں سکرین اور شاید بتا سکتے ہیں،
، میں کر سکتا ہوں کے طور پر صف اب کے مطابق ہے.
لیکن ہم ابھی تک یہ ثابت نہیں کر سکتے ہیں.
ہم اس بات کی ضمانت نہیں ہے کہ حل ہے.
لیکن یہ کہاں سویپ ہے انسداد کھیل میں آتے جا رہا ہے.
>> تو ہم نے ایک پاس مکمل کر لیا ہے.
تبدیل کردہ لسٹ کاؤنٹر 2.
تو ہم دہرانے کے لئے جا رہے ہیں پھر اس عمل،
تبدیل کردہ لسٹ انسداد 0 ہے جب تک دہرائیں.
0 ادلہ کاؤنٹر ری سیٹ.
تو ہم اسے ری سیٹ گا.
>> اب ہر ملحقہ جوڑی دیکھو.
اس ترتیب میں 1 اور 2 ہے.
2 اور 3 کے حکم میں ہیں.
3 اور 4 کے حکم میں ہیں.
تو اس وقت، ہم نے مکمل کر دیا ہے محسوس ہر ملحقہ جوڑی کو دیکھ کر،
لیکن تبدیل کردہ لسٹ انسداد اب بھی 0 ہے.
>> ہم تبدیل کرنے کی ضرورت نہیں ہے تو کسی بھی عناصر، وہ تو
کی طرف سے، حکم میں ہونا ضروری ہے اس عمل کی فضیلت.
اور اس قسم کی کارکردگی، کہ ہم کمپیوٹر کے سائنسدانوں محبت،
اب ہم اعلان کر سکتے ہیں ہے پوری صف ضروری
ہم نے نہیں کیا کیونکہ، حل کیا کسی بھی عناصر کا تبادلہ ہے.
یہ بہت اچھی بات ہے.
>> تو کیا بدترین صورت ہے بلبلا طرح سے منظر نامے؟
بدترین صورت میں صف ہے مکمل طور پر معکوس ترتیب میں،
اور ہم ہر ایک بلبلا کرنا پڑے بڑے عناصر کے تمام
سرنی بھر کے راستے.
اور ہم مؤثر طریقے سے بھی ہے بلبلا چھوٹے عناصر کے سب واپس
بھی صف میں تمام طریقہ،.
تو (ن) عناصر میں سے ہر منتقل کرنے کے لئے ہے (ن) کے عناصر کے تمام بھر میں.
تو ہے کہ بدترین صورت ہے.
بہترین صورت میں منظر نامے اگرچہ، یہ ہے
انتخاب کی طرح سے تھوڑا سا مختلف.
سرنی پہلے سے ہی ہے ہم میں جاؤ جب حل.
ہم کسی بھی بنانے کے لئے کی ضرورت نہیں ہے سب سے پہلے پاس پر سویپ.
تو ہم کو دیکھنے کے لئے ہو سکتا ہے کم عناصر، ٹھیک ہے؟
ہم اس کو دہرانے کی ضرورت نہیں ہے گنا سے زیادہ کی ایک بڑی تعداد پر عملدرآمد.
>> تو اس کا کیا مطلب ہے؟
تو کیا بدترین حالات ہے بلبلا قسم کے لئے، اور کیا
بلبلا طرح کے لئے بہترین صورت؟
آپ کو لگتا ہے کیا؟
بدترین صورت میں آپ iterate کرنا ہے تمام این عناصر ن بار بھر.
تو بدترین صورت مربع ن ہے.
>> سرنی بالکل ہے تو مطابق اگرچہ، آپ کو صرف
ایک کو دیکھنے کے لئے ہے ایک بار عناصر کے.
اور سویپ انسداد اب بھی 0 ہے، تم اس صف کے مطابق ہے کہہ سکتے ہیں.
اور تو سب سے بہتر صورت میں، یہ ہے انتخاب کے مقابلے اصل میں بہتر
sort-- یہ (ن) کے ومیگا ہے.
>> میں ڈوگ لایڈ ہوں.
یہ CS50 ہے.