1 00:00:00,000 --> 00:00:03,360 >> [موسیقی بجانے] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 ڈوگ لایڈ: ٹھیک ہے، تو بلبلا طرح ایک الگورتھم ہے 4 00:00:06,730 --> 00:00:08,730 آپ عناصر کا ایک سیٹ کو حل کرنے کے لئے استعمال کر سکتے ہیں. 5 00:00:08,730 --> 00:00:10,850 چلو اس کا کام کرتا ہے کہ کس طرح پر ایک نظر ڈالیں. 6 00:00:10,850 --> 00:00:13,240 >> تاکہ بنیادی خیال کے پیچھے بلبلا طرح ہے. 7 00:00:13,240 --> 00:00:17,340 ہم عام طور پر زیادہ منتقل کرنے کے لئے چاہتے ہیں عام طور پر درست کرنے کے لئے قابل قدر عناصر، 8 00:00:17,340 --> 00:00:20,340 اور عام طور پر قابل قدر عناصر کم بائیں، ہم توقع کریں گے کے طور پر. 9 00:00:20,340 --> 00:00:23,256 ہم کم چیزوں میں بننا چاہتا ہوں آغاز، اور اعلی چیزوں 10 00:00:23,256 --> 00:00:24,970 آخر میں ہونا. 11 00:00:24,970 --> 00:00:26,130 >> ہم یہ کیسے کرتے ہیں؟ 12 00:00:26,130 --> 00:00:28,040 ویسے pseudocode کے کوڈ میں، ہم چلو، کہہ سکتے ہیں 13 00:00:28,040 --> 00:00:30,320 ایک غیر صفر کی قیمت کرنے کے لئے ایک سویپ کاؤنٹر قائم. 14 00:00:30,320 --> 00:00:32,570 ہم ایک دوسرے میں ایسا کیوں ہم دیکھیں گے. 15 00:00:32,570 --> 00:00:36,090 اور پھر ہم نے مندرجہ ذیل کا اعادہ تبدیل کردہ لسٹ انسداد 0 ہے جب تک عمل کو، 16 00:00:36,090 --> 00:00:39,910 یا ہم سب میں کوئی سویپ تک. 17 00:00:39,910 --> 00:00:43,170 >> تبادلہ کاؤنٹر ری سیٹ 0 0 یہ پہلے سے ہی نہیں ہے تو. 18 00:00:43,170 --> 00:00:46,420 پھر ہر نظر عناصر کے ملحقہ جوڑی. 19 00:00:46,420 --> 00:00:49,550 ان دو عناصر ہیں تو نہیں کی ترتیب میں، ان کے تبادلہ، 20 00:00:49,550 --> 00:00:51,620 اور سویپ کاؤنٹر پر 1 کا اضافہ. 21 00:00:51,620 --> 00:00:53,870 آپ کے بارے میں سوچ رہے ہیں اگر آپ اسے دیکھ سے پہلے، 22 00:00:53,870 --> 00:00:57,471 یہ کم منتقل کرے گا کہ محسوس بائیں قدر عناصر 23 00:00:57,471 --> 00:01:00,720 اور اعلی، دائیں عناصر قابل قدر مؤثر طریقے سے ہم کیا کرنا چاہتے ہیں کر رہے ہیں، 24 00:01:00,720 --> 00:01:03,940 جو ان گروپوں منتقل اس طرح میں عناصر کی. 25 00:01:03,940 --> 00:01:07,035 کس طرح اس کو دیکھ دو ہمارے صف کا استعمال کرتے ہوئے نظر ہو سکتا ہے 26 00:01:07,035 --> 00:01:10,504 ہم ٹیسٹ کرنے کے لئے استعمال کیا جاتا ہے ان یلگوردمز. 27 00:01:10,504 --> 00:01:13,420 ہم ایک بار پھر یہاں ایک ناچھانٹا ہوا سرنی ہے عناصر میں سے سب کی طرف سے اس بات کا اشارہ 28 00:01:13,420 --> 00:01:14,840 سرخ رنگ میں کیا جا رہا ہے. 29 00:01:14,840 --> 00:01:17,970 اور مجھے میری تبدیل کردہ کاؤنٹر قائم ایک nonzero قیمت پر. 30 00:01:17,970 --> 00:01:20,610 میں منمانے منتخب کیا منفی 1-- یہ 0 نہیں ہے. 31 00:01:20,610 --> 00:01:23,840 ہم اس عمل دوبارہ کرنا چاہتے ہیں تبدیل کردہ لسٹ کاؤنٹر تک 0. 32 00:01:23,840 --> 00:01:26,540 مجھے میری تبدیل کردہ مقرر یہی وجہ ہے کچھ غیر صفر کی قیمت کے لئے کاؤنٹر، 33 00:01:26,540 --> 00:01:29,400 دوسری صورت میں کیونکہ تبدیل کردہ لسٹ انسداد 0 ہو جائے گا. 34 00:01:29,400 --> 00:01:31,610 ہم بھی شروع نہیں کریں گے الگورتھم کے عمل. 35 00:01:31,610 --> 00:01:33,610 تو ایک بار پھر، اقدامات are-- تبدیل کردہ لسٹ کاؤنٹر ری سیٹ 36 00:01:33,610 --> 00:01:37,900 0، پھر ہر ملحقہ دیکھو جوڑے، اور وہ حکم سے باہر ہیں تو، 37 00:01:37,900 --> 00:01:40,514 ان کا تبادلہ، اور 1 کا اضافہ تبدیل کردہ لسٹ کاؤنٹر پر. 38 00:01:40,514 --> 00:01:41,680 تو اس عمل شروع کرتے ہیں. 39 00:01:41,680 --> 00:01:44,430 تو ہمیں کیا پہلی بات یہ ہے ہم 0 ادلہ کاؤنٹر قائم 40 00:01:44,430 --> 00:01:46,660 اور پھر ہم تلاش شروع ایک ملحقہ جوڑی میں. 41 00:01:46,660 --> 00:01:49,140 >> تو ہم سب سے پہلے 5 اور 2 میں دیکھ کر شروع. 42 00:01:49,140 --> 00:01:52,410 ہم نے باہر ہیں کہ دیکھیں آرڈر اور تو ہم ان سے تبادلہ. 43 00:01:52,410 --> 00:01:53,830 اور ہم تبدیل کردہ لسٹ کاؤنٹر پر 1 کا اضافہ. 44 00:01:53,830 --> 00:01:57,860 تو اب ہماری ادلہ انسداد 1، اور 2 اور 5 تبدیل کر دیا گیا ہے. 45 00:01:57,860 --> 00:01:59,370 اب ہم پھر عمل کو دہرائیں. 46 00:01:59,370 --> 00:02:03,540 >> ہم اگلے ملحقہ جوڑی پر نظر، 5 اور وہ بھی حکم سے باہر ہو 1--، 47 00:02:03,540 --> 00:02:06,960 تو ہم ان کا تبادلہ شامل تبدیل کردہ لسٹ کاؤنٹر پر 1. 48 00:02:06,960 --> 00:02:08,900 پھر ہم 5 اور 3 میں نظر آتے. 49 00:02:08,900 --> 00:02:13,830 وہ حکم سے باہر ہیں، تو ہم تبادلہ ان کے اور ہم تبدیل کردہ لسٹ کاؤنٹر پر 1 کا اضافہ. 50 00:02:13,830 --> 00:02:15,550 پھر ہم 5 اور 6 میں نظر آتے ہیں. 51 00:02:15,550 --> 00:02:18,630 انہوں نے حکم میں ہیں، تو ہم اصل نہیں ہے کچھ اس وقت تبادلہ کرنے کی ضرورت. 52 00:02:18,630 --> 00:02:20,250 پھر ہم 6 اور 4 دیکھو. 53 00:02:20,250 --> 00:02:24,920 وہ حکم سے باہر بھی ہیں، تو ہم تبادلہ ان کے اور ہم تبدیل کردہ لسٹ کاؤنٹر پر 1 کا اضافہ. 54 00:02:24,920 --> 00:02:26,230 >> اب کیا ہوا ہے محسوس. 55 00:02:26,230 --> 00:02:29,514 ہم آخر 6 تمام راستے منتقل کر دیا گیا. 56 00:02:29,514 --> 00:02:32,180 انتخاب کی طرح میں، آپ کو ہے تو اس ویڈیو کو دیکھا، کیا ہم نے کیا تھا 57 00:02:32,180 --> 00:02:35,290 ہم آگے بڑھ رہے ہیں ختم عمارت میں سب سے چھوٹی عناصر 58 00:02:35,290 --> 00:02:39,640 سے بنیادی طور پر کے مطابق صف سب سے بڑا کرنے کے لئے، سب سے چھوٹی بائیں سے دائیں. 59 00:02:39,640 --> 00:02:43,200 بلبلا طرح کی صورت میں، ہم ہیں تو یہ خاص طور پر مندرجہ ذیل الگورتھم، 60 00:02:43,200 --> 00:02:46,720 ہم اصل میں تعمیر کیا جائے گا کے لئے جا رہے دائیں سے مطابق صف 61 00:02:46,720 --> 00:02:49,100 سب سے چھوٹی، سب سے بڑا بائیں. 62 00:02:49,100 --> 00:02:53,840 ہم مؤثر طریقے سے 6، پر bubbled ہے سب سے بڑی قیمت، ختم کرنے کے لئے تمام طریقہ. 63 00:02:53,840 --> 00:02:56,165 >> اور اس طرح ہم اب اعلان کر سکتے ہیں کہ کے مطابق ہے کہ، 64 00:02:56,165 --> 00:02:59,130 اور مستقبل میں iterations-- صف کے ذریعے جانے again-- 65 00:02:59,130 --> 00:03:01,280 اب ہم 6 پر غور کرنے کی ضرورت نہیں ہے. 66 00:03:01,280 --> 00:03:03,850 ہم صرف غور کرنا ہوگا ناچھانٹا ہوا عناصر 67 00:03:03,850 --> 00:03:06,299 جب ہم ملحقہ جوڑوں میں تلاش کر رہے ہیں. 68 00:03:06,299 --> 00:03:08,340 تو ہم نے ایک ختم کر دیا ہے بلبلا طرح سے گزرنا. 69 00:03:08,340 --> 00:03:11,941 تو اب ہم سوال پر واپس جانا، تبدیل کردہ لسٹ انسداد 0 ہے جب تک دہرائیں. 70 00:03:11,941 --> 00:03:13,690 ویسے ادلہ کاؤنٹر 4 ہے، تو ہم جا رہے ہیں 71 00:03:13,690 --> 00:03:15,410 پھر اس عمل کو دہرانے رکھنے کے لئے. 72 00:03:15,410 --> 00:03:19,180 >> ہم تبدیل کردہ لسٹ کاؤنٹر ری سیٹ کرنے کے لئے جا رہے ہیں 0، اور ہر ملحقہ جوڑی دیکھو. 73 00:03:19,180 --> 00:03:21,890 تو ہم وہ کر رہے ہیں 1-- 2 کے ساتھ شروع کریں اور حکم سے باہر ہے، تو ہم ان کا تبادلہ 74 00:03:21,890 --> 00:03:23,620 اور ہم تبدیل کردہ لسٹ کاؤنٹر پر 1 کا اضافہ. 75 00:03:23,620 --> 00:03:25,490 2 اور 3، وہ ترتیب میں ہیں. 76 00:03:25,490 --> 00:03:27,060 ہم کچھ بھی کرنے کی ضرورت نہیں ہے. 77 00:03:27,060 --> 00:03:28,420 3 اور 5 کے حکم میں ہیں. 78 00:03:28,420 --> 00:03:30,150 ہم وہاں کچھ بھی کرنے کی ضرورت نہیں ہے. 79 00:03:30,150 --> 00:03:32,515 >> 5 اور 4، وہ باہر ہیں حکم کی، اور ہم 80 00:03:32,515 --> 00:03:35,130 ان کا تبادلہ اور شامل کرنے کی ضرورت تبدیل کردہ لسٹ کاؤنٹر پر 1. 81 00:03:35,130 --> 00:03:38,880 اور اب ہم، 5 منتقل کر دیا گیا اگلے سب سے بڑا عنصر، 82 00:03:38,880 --> 00:03:40,920 ناچھانٹا ہوا حصہ کے اختتام پر. 83 00:03:40,920 --> 00:03:44,360 تو اب ہم اس کال کر سکتے ہیں مطابق حصہ کا حصہ. 84 00:03:44,360 --> 00:03:47,180 >> اب آپ دیکھ رہے ہیں سکرین اور شاید بتا سکتے ہیں، 85 00:03:47,180 --> 00:03:50,130 ، میں کر سکتا ہوں کے طور پر صف اب کے مطابق ہے. 86 00:03:50,130 --> 00:03:51,820 لیکن ہم ابھی تک یہ ثابت نہیں کر سکتے ہیں. 87 00:03:51,820 --> 00:03:54,359 ہم اس بات کی ضمانت نہیں ہے کہ حل ہے. 88 00:03:54,359 --> 00:03:56,900 لیکن یہ کہاں سویپ ہے انسداد کھیل میں آتے جا رہا ہے. 89 00:03:56,900 --> 00:03:59,060 >> تو ہم نے ایک پاس مکمل کر لیا ہے. 90 00:03:59,060 --> 00:04:00,357 تبدیل کردہ لسٹ کاؤنٹر 2. 91 00:04:00,357 --> 00:04:02,190 تو ہم دہرانے کے لئے جا رہے ہیں پھر اس عمل، 92 00:04:02,190 --> 00:04:04,290 تبدیل کردہ لسٹ انسداد 0 ہے جب تک دہرائیں. 93 00:04:04,290 --> 00:04:05,550 0 ادلہ کاؤنٹر ری سیٹ. 94 00:04:05,550 --> 00:04:06,820 تو ہم اسے ری سیٹ گا. 95 00:04:06,820 --> 00:04:09,810 >> اب ہر ملحقہ جوڑی دیکھو. 96 00:04:09,810 --> 00:04:11,880 اس ترتیب میں 1 اور 2 ہے. 97 00:04:11,880 --> 00:04:13,590 2 اور 3 کے حکم میں ہیں. 98 00:04:13,590 --> 00:04:15,010 3 اور 4 کے حکم میں ہیں. 99 00:04:15,010 --> 00:04:19,250 تو اس وقت، ہم نے مکمل کر دیا ہے محسوس ہر ملحقہ جوڑی کو دیکھ کر، 100 00:04:19,250 --> 00:04:22,530 لیکن تبدیل کردہ لسٹ انسداد اب بھی 0 ہے. 101 00:04:22,530 --> 00:04:25,520 >> ہم تبدیل کرنے کی ضرورت نہیں ہے تو کسی بھی عناصر، وہ تو 102 00:04:25,520 --> 00:04:28,340 کی طرف سے، حکم میں ہونا ضروری ہے اس عمل کی فضیلت. 103 00:04:28,340 --> 00:04:32,000 اور اس قسم کی کارکردگی، کہ ہم کمپیوٹر کے سائنسدانوں محبت، 104 00:04:32,000 --> 00:04:35,560 اب ہم اعلان کر سکتے ہیں ہے پوری صف ضروری 105 00:04:35,560 --> 00:04:38,160 ہم نے نہیں کیا کیونکہ، حل کیا کسی بھی عناصر کا تبادلہ ہے. 106 00:04:38,160 --> 00:04:40,380 یہ بہت اچھی بات ہے. 107 00:04:40,380 --> 00:04:43,260 >> تو کیا بدترین صورت ہے بلبلا طرح سے منظر نامے؟ 108 00:04:43,260 --> 00:04:46,240 بدترین صورت میں صف ہے مکمل طور پر معکوس ترتیب میں، 109 00:04:46,240 --> 00:04:49,870 اور ہم ہر ایک بلبلا کرنا پڑے بڑے عناصر کے تمام 110 00:04:49,870 --> 00:04:51,780 سرنی بھر کے راستے. 111 00:04:51,780 --> 00:04:55,350 اور ہم مؤثر طریقے سے بھی ہے بلبلا چھوٹے عناصر کے سب واپس 112 00:04:55,350 --> 00:04:57,050 بھی صف میں تمام طریقہ،. 113 00:04:57,050 --> 00:05:01,950 تو (ن) عناصر میں سے ہر منتقل کرنے کے لئے ہے (ن) کے عناصر کے تمام بھر میں. 114 00:05:01,950 --> 00:05:04,102 تو ہے کہ بدترین صورت ہے. 115 00:05:04,102 --> 00:05:05,810 بہترین صورت میں منظر نامے اگرچہ، یہ ہے 116 00:05:05,810 --> 00:05:07,880 انتخاب کی طرح سے تھوڑا سا مختلف. 117 00:05:07,880 --> 00:05:10,040 سرنی پہلے سے ہی ہے ہم میں جاؤ جب حل. 118 00:05:10,040 --> 00:05:12,550 ہم کسی بھی بنانے کے لئے کی ضرورت نہیں ہے سب سے پہلے پاس پر سویپ. 119 00:05:12,550 --> 00:05:14,940 تو ہم کو دیکھنے کے لئے ہو سکتا ہے کم عناصر، ٹھیک ہے؟ 120 00:05:14,940 --> 00:05:18,580 ہم اس کو دہرانے کی ضرورت نہیں ہے گنا سے زیادہ کی ایک بڑی تعداد پر عملدرآمد. 121 00:05:18,580 --> 00:05:19,540 >> تو اس کا کیا مطلب ہے؟ 122 00:05:19,540 --> 00:05:22,390 تو کیا بدترین حالات ہے بلبلا قسم کے لئے، اور کیا 123 00:05:22,390 --> 00:05:25,330 بلبلا طرح کے لئے بہترین صورت؟ 124 00:05:25,330 --> 00:05:27,770 آپ کو لگتا ہے کیا؟ 125 00:05:27,770 --> 00:05:32,420 بدترین صورت میں آپ iterate کرنا ہے تمام این عناصر ن بار بھر. 126 00:05:32,420 --> 00:05:34,220 تو بدترین صورت مربع ن ہے. 127 00:05:34,220 --> 00:05:36,550 >> سرنی بالکل ہے تو مطابق اگرچہ، آپ کو صرف 128 00:05:36,550 --> 00:05:38,580 ایک کو دیکھنے کے لئے ہے ایک بار عناصر کے. 129 00:05:38,580 --> 00:05:42,670 اور سویپ انسداد اب بھی 0 ہے، تم اس صف کے مطابق ہے کہہ سکتے ہیں. 130 00:05:42,670 --> 00:05:45,780 اور تو سب سے بہتر صورت میں، یہ ہے انتخاب کے مقابلے اصل میں بہتر 131 00:05:45,780 --> 00:05:49,230 sort-- یہ (ن) کے ومیگا ہے. 132 00:05:49,230 --> 00:05:50,270 >> میں ڈوگ لایڈ ہوں. 133 00:05:50,270 --> 00:05:52,140 یہ CS50 ہے. 134 00:05:52,140 --> 00:05:54,382