1 00:00:00,500 --> 00:00:02,840 [Powered by Google Translate] [بلبلا ترتیب دیں] 2 00:00:02,840 --> 00:00:04,560 [جیکسن STEINKAMP ہارورڈ یونیورسٹی] 3 00:00:04,560 --> 00:00:07,500 اس [CS50 ہے. CS50TV] 4 00:00:08,000 --> 00:00:11,730 بلبلا ترتیب دیں چھںٹائی الگورتھم کی ایک مثال ہے - 5 00:00:11,730 --> 00:00:14,460 ایسا ہے، عناصر کا ایک سیٹ میں حل کرنے کے لئے ایک طریقہ کار 6 00:00:14,460 --> 00:00:15,840 صعودی یا نزولی ترتیب. 7 00:00:15,840 --> 00:00:18,710 مثال کے طور پر، اگر آپ کو ایک صف ترتیب کرنا چاہتے تھے کی تعداد پر مشتمل 8 00:00:18,710 --> 00:00:23,060 [3، 5، 2، 9]، بلبلا کی ترتیب کا صحیح عمل درآمد لوٹ آئیں گے 9 00:00:23,060 --> 00:00:26,260 کے مطابق [2، 3، 5، 9] صف صعودی میں. 10 00:00:26,260 --> 00:00:28,850 اب، میں pseudocode میں کی وضاحت کرنے جا رہا ہوں کس طرح الگورتھم کام کرتا ہے. 11 00:00:28,850 --> 00:00:34,000 >> چلو کا کہنا ہے کہ ہم 5 integers کی ایک فہرست چھانٹ رہا ہے - 3، 2، 9، 6، اور 5. 12 00:00:34,000 --> 00:00:37,650 الگورتھم پہلے دو عناصر، 3 اور 2 میں دیکھ کر شروع ہوتا ہے، 13 00:00:37,650 --> 00:00:40,850 جانچ پڑتال اور اگر وہ ایک دوسرے کے رشتہ دار آرڈر سے باہر ہو گیا. 14 00:00:40,850 --> 00:00:43,150 وہ ہیں - 3 2 سے بڑا ہے. 15 00:00:43,150 --> 00:00:45,190 آروہی ترتیب میں، وہ دوسرے کے ارد گرد راستہ ہونا چاہئے. 16 00:00:45,190 --> 00:00:46,610 تو، ہم ان سے تبادلہ. 17 00:00:46,610 --> 00:00:49,760 [2، 3، 9، 6، 5]: اب فہرست اس طرح لگ رہا ہے. 18 00:00:49,760 --> 00:00:52,450 >> اگلا، ہم نے دوسری اور تیسری عناصر، 3 اور 9 میں نظر آتے ہیں. 19 00:00:52,450 --> 00:00:55,770 انہوں نے ایک دوسرے کے رشتہ دار صحیح حکم میں ہیں. 20 00:00:55,770 --> 00:00:58,800 3 یہ ہے، تو 9 سے کم الگورتھم ان تبادلہ نہیں ہوتا. 21 00:00:58,800 --> 00:01:01,900 اگلا، ہم نے 9 اور 6 بجے لگ رہی ہو. انہوں نے حکم سے باہر ہو گیا. 22 00:01:01,900 --> 00:01:04,260 >> تو، ہم ان کی وجہ 9 6 سے بڑھ کر ہے پر تبادلہ کرنے کی ضرورت ہے. 23 00:01:04,260 --> 00:01:08,840 آخر میں، ہم نے گزشتہ دو integers، 9 اور 5 میں نظر آتے ہیں. 24 00:01:08,840 --> 00:01:10,850 وہ حکم سے باہر ہو، تو وہ تبدیل ہونا چاہئے. 25 00:01:10,850 --> 00:01:13,360 فہرست کے ذریعے پہلے مکمل پاس کرنے کے بعد، 26 00:01:13,360 --> 00:01:17,140 [2، 3، 6، 5، 9]: یہ اس طرح لگ رہا ہے. 27 00:01:17,140 --> 00:01:19,690 برا نہیں ہے. یہ تقریبا کے مطابق ہے. 28 00:01:19,690 --> 00:01:22,450 لیکن ہم فہرست کے ذریعے دوبارہ چلانے کے اسے مکمل طور پر حل کرنے کی ضرورت ہے. 29 00:01:22,450 --> 00:01:29,250 دو 3 سے کم ہے، تو ہم ان سے تبادلہ نہیں کرتے. 30 00:01:29,250 --> 00:01:31,700 >> تین 6 سے کم ہے، تو ہم ان سے تبادلہ نہیں کرتے. 31 00:01:31,700 --> 00:01:35,500 چھ 5 سے زیادہ ہے. ہم تبدیل. 32 00:01:35,500 --> 00:01:38,460 چھ 9 سے کم ہے. ہم نہیں تبادلہ ہے. 33 00:01:38,460 --> 00:01:42,170 دوسرے سے گزرنے کے بعد، یہ اس طرح لگ رہا ہے: [2، 3، 5، 6، 9]. ٹھیک ہے. 34 00:01:42,170 --> 00:01:44,680 اب، لکھنے pseudocode میں. 35 00:01:44,680 --> 00:01:48,450 بنیادی طور پر، فہرست میں ہر عنصر کے لئے، ہم اس کو دیکھنے کے لئے کی ضرورت ہے 36 00:01:48,450 --> 00:01:50,060 اور براہ راست اس کے حق کے عنصر. 37 00:01:50,060 --> 00:01:53,420 اگر وہ حکم سے باہر ایک دوسرے کے رشتہ دار ہیں - یہ ہے کہ، اگر بائیں عناصر 38 00:01:53,420 --> 00:01:56,810 دائیں جانب ایک سے زیادہ ہے - ہم دو عناصر تبادلہ کرنا چاہئے. 39 00:01:56,810 --> 00:02:01,270 >> ہم نے فہرست کے ہر عنصر کے لئے ایسا کرتے ہیں، اور ہم اس کے ذریعے ایک پاس کر دیا ہے. 40 00:02:01,270 --> 00:02:05,160 اب ہم صرف پاس کے ذریعے کافی وقت کی فہرست کو یقینی بنانے کے لئے کرنا ہے 41 00:02:05,160 --> 00:02:06,480 مکمل طور پر ہے، کے مطابق مناسب طریقے سے ہے. 42 00:02:06,480 --> 00:02:08,889 لیکن ہم نے کتنی بار کی فہرست کے ذریعے منتقل کی ہے 43 00:02:08,889 --> 00:02:10,400 اس بات کی ضمانت ہے کہ ہم کیا کر رہے ہیں؟ 44 00:02:10,400 --> 00:02:14,730 ٹھیک ہے، بدترین حالات کی صورت یہ ہے اگر ہم ایک مکمل طور پر پیچھے کی طرف کی فہرست ہے. 45 00:02:14,730 --> 00:02:17,840 اس وقت یہ throughs کے پاس کی ایک بڑی تعداد میں تعداد کے برابر لگتا ہے 46 00:02:17,840 --> 00:02:19,730 1 (ن) کے عناصر کے. 47 00:02:19,730 --> 00:02:24,720 اگر اس کا کوئی مطلب نہیں ہے intuitively، ایک سادہ کیس کے بارے میں سوچ - فہرست [2، 1]. 48 00:02:24,720 --> 00:02:28,430 >> یہ درست طریقے سے ترتیب کے لئے ایک پاس کے ذریعے لے جا رہا ہے. 49 00:02:28,430 --> 00:02:33,060 [3، 2، 1] - سب سے بری حالت ہے کہ 3 عناصر کے ساتھ پیچھے کی طرف کے مطابق، 50 00:02:33,060 --> 00:02:34,830 اس طرح 2 تکرار لے جا رہا ہے. 51 00:02:34,830 --> 00:02:37,980 ایک iteration کے بعد [2، 1، 3] ہے. 52 00:02:37,980 --> 00:02:39,550 دوسری پیداوار کے مطابق صف [1، 2، 3]. 53 00:02:39,550 --> 00:02:43,350 تو آپ کو معلوم ہے کہ تم عام طور پر صف کے ذریعے جانے کے لئے نہیں،، 54 00:02:43,350 --> 00:02:46,790 ن 1 بار جہاں N صف میں عناصر کی تعداد ہے کے مقابلے میں زیادہ ہے. 55 00:02:47,090 --> 00:02:50,470 یہ بلبلا ترتیب دیں کہا جاتا ہے کیونکہ سب سے بڑا عناصر 'بلبلا اپ کرتے ہیں 56 00:02:50,470 --> 00:02:51,950 بہت تیزی سے حق کو. 57 00:02:51,950 --> 00:02:53,980 اصل میں، یہ الگورتھم بہت دلچسپ رویہ ہے. 58 00:02:53,980 --> 00:02:57,410 >> پوری صف کے ذریعے میٹر تکرار کے بعد، 59 00:02:57,410 --> 00:02:59,000 rightmost م عناصر کی ضمانت دی ہیں 60 00:02:59,000 --> 00:03:01,000 ان کی صحیح جگہ میں حل کیا جائے گا. 61 00:03:01,000 --> 00:03:02,280 اگر آپ کو خود کے لئے یہ دیکھنا چاہتے ہیں، 62 00:03:02,280 --> 00:03:05,500 ہم اسے ایک مکمل طور پر پیچھے کی طرف [9، 6، 5، 3، 2] فہرست میں کوشش کر سکتے ہیں. 63 00:03:05,500 --> 00:03:08,220 ، کی مکمل فہرست کے ذریعے ایک پاس کے بعد، 64 00:03:08,220 --> 00:03:09,220 [لکھنے کی آواز] 65 00:03:09,220 --> 00:03:18,790 [6، 9، 5، 3، 2،]، [6، 5، 9، 3 2،]، [6، 5، 3، 9 2،]، [6، 5، 3، 2، 9] 66 00:03:18,790 --> 00:03:21,250 rightmost 9 عنصر اس کی مناسب جگہ ہے. 67 00:03:21,250 --> 00:03:24,760 پاس کے ذریعے دوسرے کے بعد، 6 ہے 'bubbled اپ' 68 00:03:24,760 --> 00:03:26,220 دوسری rightmost جگہ. 69 00:03:26,220 --> 00:03:28,840 6 - 9 - حق دونوں عناصر کو ان کی صحیح جگہوں میں ہو جائے گا 70 00:03:28,840 --> 00:03:30,580 پہلے دو پاس throughs کے بعد. 71 00:03:30,580 --> 00:03:32,590 >> تو، یہ ہم کس طرح الگورتھم کو بہتر بنانے کے لئے استعمال کر سکتے ہیں؟ 72 00:03:32,590 --> 00:03:34,850 ٹھیک ہے، صف کے ذریعے ایک iteration کے بعد 73 00:03:34,850 --> 00:03:37,690 ہم rightmost عنصر چیک کرنے کے لیے اصل میں ضرورت نہیں ہے 74 00:03:37,690 --> 00:03:39,200 کیونکہ ہم جانتے ہیں کے مطابق ہے. 75 00:03:39,200 --> 00:03:43,050 دو تکرار کے بعد، ہم اس بات کا یقین کر لیں کہ rightmost دو عناصر جگہ میں ہیں کے لئے جانتے ہیں. 76 00:03:43,050 --> 00:03:48,260 لہذا، عام طور پر، مکمل صف کے ذریعے K تکرار کے بعد 77 00:03:48,260 --> 00:03:51,550 آخری K عناصر پرکھنے کے بے کار ہے کیونکہ ہم جانتے ہیں 78 00:03:51,550 --> 00:03:52,360 وہ پہلے ہی صحیح جگہ میں ہیں. 79 00:03:52,360 --> 00:03:54,870 >> تو اگر آپ کو (ن) کے عناصر کا ایک صف چھںٹائی کر رہے ہیں، 80 00:03:54,870 --> 00:03:57,870 پہلے iteration - you'll عناصر کے سب الگ الگ ہے - پہلے ن 0. 81 00:03:57,870 --> 00:04:04,170 دوسری iteration پر، آپ کو عناصر کے سب لیکن گزشتہ کی طرف دیکھنے کی ضرورت ہوگی - 82 00:04:04,170 --> 00:04:07,090 پہلے این 1. 83 00:04:07,090 --> 00:04:10,520 ایک اور اصلاح کی اگر فہرست پہلے ہی کے مطابق ہے چیک کرنے کے لیے ہو سکتا ہے 84 00:04:10,520 --> 00:04:11,710 ہر iteration کے بعد. 85 00:04:11,710 --> 00:04:13,900 اگر یہ پہلے سے ہی حل ہے، ہم زیادہ تکرار کرنے کی ضرورت نہیں ہے 86 00:04:13,900 --> 00:04:15,310 فہرست کے ذریعے. 87 00:04:15,310 --> 00:04:16,220 ہم یہ کیسے کر سکتے ہیں؟ 88 00:04:16,220 --> 00:04:19,360 ٹھیک ہے، اگر ہم ایک فہرست کے پاس کے ذریعے کسی بھی سویپ نہیں ہے 89 00:04:19,360 --> 00:04:22,350 یہ واضح ہے کہ فہرست میں پہلے ہی کے مطابق کیا گیا تھا کیونکہ ہم کچھ بھی تبادلہ نہیں کیا. 90 00:04:22,350 --> 00:04:24,160 تو ہم ضرور دوبارہ ترتیب کی ضرورت نہیں ہے. 91 00:04:24,160 --> 00:04:27,960 >> شاید آپ کو ایک پرچم کہا جاتا ہے 'کے مطابق نہیں متغیر ابتدا کر سکتا ہے 92 00:04:27,960 --> 00:04:30,990 اور درست کرنے کے لئے اسے تبدیل جھوٹے اگر آپ پر کسی بھی عناصر کا تبادلہ ہے 93 00:04:30,990 --> 00:04:32,290 صف کے ذریعے ایک iteration. 94 00:04:32,290 --> 00:04:35,350 یا اسی طرح، ایک انسداد شمار کتنے سویپ تم 95 00:04:35,350 --> 00:04:37,040 کسی بھی iteration پر. 96 00:04:37,040 --> 00:04:40,040 iteration کے آخر میں، اگر آپ عناصر کا کوئی تبادلہ نہیں کیا، 97 00:04:40,040 --> 00:04:41,780 تم جانتے ہو کی فہرست پہلے ہی حل ہے اور تم نے کیا کیا کر رہے ہیں. 98 00:04:41,780 --> 00:04:44,090 بلبلا ترتیب دیں، دیگر چھنٹائی یلگوردمز کی طرح ہو، کر سکتے ہیں 99 00:04:44,090 --> 00:04:46,960 کسی بھی عناصر ہیں جو ایک آرڈر کا طریقہ ہے کے لئے کام کرنے tweaked. 100 00:04:46,960 --> 00:04:50,610 >> یہ دو عناصر دیا ہے آپ کو ایک کہنے کا ایک طریقہ ہے، اگر پہلے ایک 101 00:04:50,610 --> 00:04:53,770 سے، یا اس کے برابر دوسرے سے کم زیادہ ہے. 102 00:04:53,770 --> 00:04:56,870 مثال کے طور پر، آپ کہہ رہی کی طرف سے حروف تہجی کے حروف ترتیب کر سکتے ہیں 103 00:04:56,870 --> 00:05:00,520 کہ ایک 00:05:03,830 یا آپ کو ہفتے کے دنوں میں الگ الگ جہاں اتوار کو پیر کے روز سے بھی کم ہے 105 00:05:03,830 --> 00:05:05,110 جو منگل کے روز سے بھی کم ہے. 106 00:05:05,110 --> 00:05:09,630 >> بلبلا ترتیب دیں کی طرف سے کوئی ایک بہت ہی موثر یا فاسٹ چھنٹائی الگورتھم کا مطلب ہے کہ. 107 00:05:09,630 --> 00:05:12,370 اس رن ٹائم بدترین بگ این اے ² 108 00:05:12,370 --> 00:05:14,810 کیونکہ آپ ایک فہرست کے ذریعے (ن) کے تکرار کرنے کی ہے 109 00:05:14,810 --> 00:05:18,430 تمام این عناصر کی جانچ پڑتال ہر پاس کے ذریعے، nxn ن = ². 110 00:05:18,430 --> 00:05:22,730 یہ چلت وقت کا مطلب یہ ہے کہ آپ کے عناصر کی تعداد کے طور پر اضافہ چھںٹائی کر رہے ہیں، 111 00:05:22,730 --> 00:05:24,330 چلت وقت quadratically بڑھ جاتا ہے. 112 00:05:24,330 --> 00:05:27,330 >> لیکن اگر آپ کے پروگرام کی کارکردگی ایک بڑا مسئلہ نہیں ہے 113 00:05:27,330 --> 00:05:29,550 یا اگر آپ صرف عناصر کی ایک چھوٹی سی تعداد میں چھانٹ رہا ہے کر رہے ہیں، 114 00:05:29,550 --> 00:05:31,660 آپ ببل ترتیب دیں مفید ہو سکتا ہے کیونکہ 115 00:05:31,660 --> 00:05:33,360 یہ آسان چھانٹ رہا ہے الگورتھم میں سے ایک ہے سمجھنے کی 116 00:05:33,360 --> 00:05:34,250 کوڈ اور. 117 00:05:34,250 --> 00:05:37,270 یہ بھی ایک عظیم نظریاتی ترجمہ کے ساتھ تجربہ حاصل کرنے کا ایک طریقہ ہے 118 00:05:37,270 --> 00:05:40,220 اصل کام کاج کے کوڈ میں الگورتھم ہے. 119 00:05:40,220 --> 00:05:43,000 ٹھیک ہے، یہ آپ کے لئے بلبلا ترتیب دیں. دیکھ کے لئے شکریہ. 120 00:05:43,000 --> 00:05:44,000 CS50.TV