[موسیقی بجانے] 

ڈوگ لایڈ: ٹھیک ہے، تو ایک ضم قسم ابھی تک کسی دوسرے الگورتھم ہے ہم کو حل کرنے کے لئے استعمال کر سکتے ہیں ایک سرنی کے عناصر. ہم دیکھیں گے کے طور پر لیکن، یہ ہے ایک بہت بنیادی فرق انتخاب کی طرح، بلبلا سے ترتیب دیں، اور اندراج کی طرح یہ واقعی بہت ہوشیار بنانے. 

ضم کے پیچھے بنیادی خیال قسم چھوٹے arrays کے حل کرنے کے لئے ہے اور پھر ان arrays کے جمع ایک ساتھ مل کر، یا غار ضم اس وجہ سے کے مطابق ترتیب میں نام بتاو. قسم ہے اس طرح ضم اس آلے کا فائدہ کی طرف سے ہے کیا ہے جس میں، تکرار نامی ہم جلد ہی کے بارے میں بات کرنے جا رہے ہیں لیکن ہم سچ میں ابھی تک کے بارے میں بات نہیں کی ہے. 

یہاں ضم طرح کے پیچھے بنیادی خیال ہے. ، صف کے بائیں نصف ترتیب N سنبھالنے 1 سے زیادہ ہے. اور مجھے کہنا ہے کہ جب اس کا کیا مطلب N سنبھالنے، 1 اس سے بڑا ہے میرے خیال میں ہمیں اتفاق کر سکتے ہیں لگتا ہے کہ ایک صف ہے صرف ایک عنصر پر مشتمل ہے، یہ حل ہے. ہم اصل میں ضرورت نہیں ہے اس کے لئے کچھ بھی کرنے کو. ہم صرف یہ حل کرنے کا اعلان کر سکتے. یہ صرف ایک عنصر ہے. 

تو pseudocode، پھر، ہے ، صف کے بائیں نصف ترتیب پھر دائیں نصف صف ترتیب، پھر دوسرے کے ساتھ دو حصوں کو ضم. اب، پہلے سے ہی آپ ہو سکتا ہے سوچ، اس قسم کی صرف the-- آپ کو ڈال رہے ہیں کی طرح لگتا ہے آپ اصل میں کچھ بھی نہیں کر رہے ہیں. آپ کو بائیں ترتیب کہہ رہے نصف، صحیح نصف ترتیب، لیکن آپ نہیں کہہ رہے ہیں مجھے تم اسے کس طرح کر رہے ہیں. 

لیکن جب تک کے طور پر یاد رکھیں کہ ایک صف میں ایک واحد عنصر ہے، ہم اسے حل کا اعلان کر سکتے. اس کے بعد ہم صرف ان کے ساتھ جمع کر سکتے ہیں. اور یہ کہ اصل میں ہے ضم طرح کے پیچھے بنیادی خیال، تاکہ اس کو توڑنے کے لئے ہے آپ arrays کے سائز ایک ہیں. اور پھر آپ وہاں سے تعمیر نو. 

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

تو ہم کے طور پر اسی صف ہے دیگر چھنٹائی الگورتھم ویڈیوز تم نے دیکھا ہے تو غار چھ عنصر سرنی. اور یہاں ہمارے pseudocode کوڈ طرح ہے بائیں نصف، صحیح نصف ترتیب، دونوں حصوں کو ضم. تو یہ بہت تاریک اینٹوں کی سرخ ڈالیں صف اور اس کے بائیں نصف ترتیب. 

کچھ وقت کے لئے تو، ہم جا رہے ہیں دائیں جانب سامان کو نظر انداز کرنا. یہ وہاں ہے، لیکن ہم ہیں ابھی تک نہیں ہے کہ قدم پر. ہم ہیں نہیں قسم صف کے دائیں نصف. ہم قسم بائیں پر ہیں صف کے نصف. اور صرف خاطر کا ایک چھوٹا سا زیادہ ہونے کی وجہ سے واضح، تو میں رجوع کر سکتے ہیں کیا مرحلے پر ہم پر ہو، میں سوئچ کرنے کے لئے جا رہا ہوں سنتری اس سیٹ کا رنگ. اب، ہم اب بھی کے بارے میں بات کر رہے ہیں اصل صف کے اسی بائیں نصف. لیکن میں کرنے کے قابل کیا جا رہا ہے کی طرف سے امید ہے کہ رہا ہوں مختلف اشیاء کی رنگ کی طرف رجوع، یہ ایک چھوٹا سا زیادہ بنا دیں گے یہاں کیا ہو رہا ہے صاف. 

ٹھیک ہے، تو اب ہم نے ایک تین عنصر سرنی. ہم اس کے بائیں نصف ترتیب کیسے اب بھی یہ قدم ہے جو سرنی،؟ ہم بائیں کو حل کرنے کی کوشش کر رہے ہیں اینٹوں کی سرخ صف کے نصف بائیں نصف جن میں میں اب سنتری رنگ ہے. 

ٹھیک ہے، ہم کوشش کر سکتے ہیں اور پھر اس عمل کو دہرائیں. تو ہم میں اب بھی ہیں الگ الگ کرنے کی کوشش کر کے وسط مکمل صف کے بائیں نصف. کے بائیں نصف سرنی، میں صرف جا رہا ہوں منمانے فیصلہ کرنا کہ بائیں نصف دائیں نصف سے چھوٹا ہو جائے گا، اس لئے ہوتا ہے کیونکہ تین عناصر پر مشتمل ہوتے ہیں. 

اور تو میں نے اس کا کہنا ہے کہ جا رہا ہوں بائیں نصف صف کے بائیں نصف صرف عنصر پانچ ہے. پانچ، ایک عنصر ہونے صف، ہم اس کو حل کرنے کے لئے کس طرح جانتے ہیں. اور اس طرح پانچ کے مطابق ہے. ہم صرف اس کا اعلان کرنے جا رہے ہیں. یہ ایک واحد عنصر صف ہے. 

تو کیا اب ہم حل ہے بائیں half-- کے بائیں نصف یا بلکہ، ہم کے مطابق ہے سنتری کے بائیں نصف. تو اب، میں حکم کے لئے اب بھی مکمل مجموعی طور پر صف کے بائیں نصف، ہم صحیح نصف ترتیب کرنے کی ضرورت ہے سنتری، یا اس چیز کی. ہم اس کس طرح کروں؟ ٹھیک ہے، ہم ایک دو عنصر سرنی ہے. تو ہم بائیں نصف ترتیب کر سکتے ہیں دو ہے جو صف کے. دو ایک عنصر ہے. تو یہ پہلے سے طے شدہ کی طرف سے حل ہے. پھر ہم صحیح نصف ترتیب کر سکتے ہیں سرنی، ایک کے اس حصے کی. یہ ڈیفالٹ کی طرف سے کی طرح ہے. 

اب یہ پہلی بار ہوا ہے ہم ضم قدم تک پہنچ گئے ہیں. ہم اگرچہ، مکمل کر لیا ہے اب ہم قسم کی down-- در رہے اور یہ کہ مشکل کی طرح ہے تکرار کے ساتھ بات، ہے آپ کو آپ کے رکھنے کے لئے کی ضرورت ہے ہم کہاں ہیں کے بارے میں سربراہ. تو ہم بائیں بازو کی قسم ہے سنتری حصے کی نصف. 

اور اب، ہم چھنٹائی کے درمیان میں ہیں سنتری حصے کے دائیں نصف. اور اس عمل میں، ہم ہیں قدم پر ہونے کے بارے میں، دونوں حصوں کو ضم. ہم دو حصوں میں نظر آتے ہیں تو صف کے، ہم دو اور ایک دیکھیں. جس عنصر چھوٹا ہے؟ ایک. 

پھر جس کے عنصر چھوٹا ہے؟ ٹھیک ہے، یہ دو یا کچھ بھی نہیں ہے. تو یہ دو ہے. تو اب، صرف ایک بار پھر تیار کرنے کے لئے ہم سیاق و سباق میں ہیں جہاں، ہم حل ہے سنتری کے بائیں نصف اور اصل کے دائیں نصف. میں رنگ تبدیل کر دیا ہے جانتے ہیں ہم کہاں تھے پھر، لیکن اس کے. اور اس کی وجہ میں نے یہ کیا اس عمل کی وجہ سے ہے نیچے iterating کر، جا رکھنے کے لئے جا رہا. ہم بائیں کے مطابق ہے سابق سنتری کے نصف اور سابق اورنج کے دائیں نصف. 

اب، ہم ان ضم کرنے کی ضرورت ایک دوسرے کے ساتھ بھی دو حصوں. یہی ہے جو ہم پر ہیں قدم ہے. تو ہم سب پر غور اب سبز ہیں کہ عناصر، اصل صف کے بائیں نصف. اور ہم ان ضم اسی عمل کو استعمال کر رہے ہیں ہم دو ولی کے لئے کیا اور ایک پہلے صرف ایک لمحے. 

بائیں نصف، سب سے چھوٹی بائیں نصف پر عنصر پانچ ہے. سب سے چھوٹی عنصر پر دائیں نصف سے ایک ہے. ان میں سے کون سا چھوٹا ہے؟ ایک. 

سب سے چھوٹی عنصر پر بائیں نصف پانچ ہے. سب سے چھوٹی عنصر پر دائیں نصف دو. سب سے چھوٹی ہے؟ دو. اور پھر آخر میں پانچ اور کچھ بھی نہیں، ہم پانچ کہہ سکتے ہیں. 

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

اصل کو یاد ہوگا کہ آرڈر پانچ، دو، ایک تھا. اس عمل کے ذریعے جا کر اور نیچے nesting اور بار بار، مسئلہ کو توڑنے کے لئے جاری نیچے چھوٹے اور چھوٹے حصوں میں، اب ہم مکمل کر لیا ہے pseudocode کی ایک قدم پورے اغاز سرنی کے لئے. ہم اس کے بائیں نصف حل ہے. 

تو اب وہاں منجمد دو. اور اب صحیح طرح دو اصل صف کے نصف. اور ہمیں ایسا کرنے کے لئے جا رہے ہیں اسی تکراری سے گزر رہا چیزوں کو توڑنے کے عمل اور پھر ان کے ساتھ ضم. 

تو کے بائیں نصف سرخ، یا بائیں نصف اصل کے دائیں نصف کے سرنی، میں کہنے جا رہا ہوں تین ہے. ایک بار پھر، میں یہاں مسلسل رہا ہوں. آپ ایک عجیب ہیں، تو عناصر کی تعداد، اس واقعی کوئی فرق نہیں پڑتا آپ کو چھوڑ دیا ایک چھوٹے بنانے یا دائیں چھوٹے ایک. 

کیا فرق پڑتا ہے جب تم نے اس انعقاد میں اس مسئلہ کا سامنا ایک ضم، آپ مسلسل ہونے کی ضرورت ہے. آپ کو یا تو ہمیشہ کی ضرورت ہے ایک بائیں جانب چھوٹے بنانے یا ہمیشہ بنانے کی ضرورت ہے دائیں جانب چھوٹے. یہاں، میں نے ہمیشہ آپ کو منتخب کیا ہے بائیں جانب چھوٹے بنانے جب میرے سرنی، یا میرے ذیلی سرنی، ایک عجیب سائز کی ہے. 

تین ایک عنصر ہے، اور تو اس کے مطابق ہے. ہم اس مفروضے لیوریجڈ ہے ہمارے پورے عمل کے دوران اب تک. تو اب صحیح طرح دو صحیح نصف میں سے نصف، یا سرخ کے دائیں نصف. 

ایک بار پھر، ہم نے اس کے نیچے تقسیم کرنے کی ضرورت. یہ ایک واحد عنصر سرنی نہیں ہے. ہم اسے حل کا اعلان نہیں کر سکتے ہیں. اور تو سب سے پہلے، ہم جا رہے ہیں بائیں نصف کو حل کرنے. 

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

ایک بار پھر، کیا ہم اس وقت کیا ہے؟ ہم بائیں کے مطابق ہے دائیں نصف کے نصف. یا اصل میں واپس جانے وہاں تھے کہ رنگ، ہم بائیں کے مطابق ہے معتدل سرخ رنگ کی نصف. یہ اصل میں ایک سیاہ اینٹوں تھا سرخ اور اب یہ ایک معتدل لال ہے، یا یہ ایک معتدل سرخ تھا. 

اور پھر ہم حل ہے معتدل سرخ کے دائیں نصف. اب، اچھی طرح سے، وہ صرف، پھر سبز ہیں ہم نے ایک عمل کے ذریعے جا رہے ہیں کیونکہ. اور ہم دوبارہ کرنا پڑے اس سے زیادہ اور اس سے زیادہ. 

تو اب ہم ان ضم کر سکتے ہیں ایک دوسرے کے ساتھ دو حصوں. اور یہ کہ ہم یہاں کیا ہے. سیاہ لائن تو بائیں نصف تقسیم اور اس طرح حصے کے دائیں نصف. 

ہم سب سے چھوٹی قیمت کا موازنہ صف کے بائیں جانب یا مجھے معاف، سب سے چھوٹی بائیں نصف کی قدر حق کی چھوٹی قیمت کے نصف اور تین چھوٹے ہے کہ مل جائے. اور اب ایک اصلاح کا تھوڑا سا، ہے نا؟ کچھ بھی نہیں حقیقت ہے بائیں جانب پر چھوڑ دیا. 

باقی کچھ بھی نہیں ہے بائیں جانب، تو ہم مؤثر طریقے سے کر سکتے ہیں ہم اعلان کر سکتے ہیں move-- باقی اصل ہے حل اور صرف اس سمت کچھ بھی نہیں ہے کیونکہ، پر کے خلاف آپس میں موازنہ کرنے کے لئے اور. اور ہم جانتے ہیں کہ دائیں جانب دائیں طرف کے مطابق ہے. 

ٹھیک ہے، تو اب ایک بار پھر منجمد دو اور ہم کہانی میں ہیں جہاں پتہ. مجموعی طور پر صف میں، ہم کیا حاصل کیا ہے؟ ہم اصل میں پورا کر دیا ہے اب ایک اور قدم دو قدم. ہم بائیں نصف حل، اور ہم صحیح نصف حل. 

تو اب، رہتا ہے کہ ہم سب کے لئے ہے ایک دوسرے کے ساتھ ان دو حصوں کو ضم کرنے کے لئے. تو ہم سب سے کم قابل قدر کا موازنہ سرنی میں سے ہر ایک نصف کے عنصر اور اس کے نتیجے میں آگے بڑھنے. ایک تین سے کم ہے، تو ایک ہے. 

دو تین کے مقابلے میں کم ہے، تاکہ دونوں جاتا. تین 5 سے بھی کم ہے، تو تین ہے. چار 5 سے بھی کم ہے، تو چار جاتا. اس کے بعد پانچ، چھ کے مقابلے میں کم ہے اور چھ تمام کہ رہتا ہے. 

اب، میں جانتا ہوں، کہ اقدامات کی ایک بہت تھا. اور ہم نے ایک بہت کچھ چھوڑ دیا ہے ہمارے تناظر میں میموری کی. اور وہ لوگ جو بھوری رنگ چوکوں ہیں کیا ہے. کہ ایک لیا طرح اور یہ شاید محسوس کیا اندراج کی طرح سے زیادہ بہت، بلبلا قسم، یا انتخاب طرح. 

لیکن اصل میں، کی وجہ سے ایک ان کے عمل میں بہت اسی ہیں وقت میں ہو رہی ہیں جس میں، پھر، ہم کریں گے کچھ ہے ہم کے بارے میں بات کرتے ہیں کے بارے میں بات مستقبل میں تکرار video-- اصل میں اس الگورتھم واضح طور پر بنیادی طور پر ہے کچھ کے مقابلے میں مختلف ہم نے پہلے دیکھا ہے لیکن نمایاں طور پر بھی ہے زیادہ موثر. 

ایسا کیوں ہے؟ ویسے، سب سے زیادہ میں صورت، ہم ن عناصر کو تقسیم کرنے کے لئے اور پھر ان میٹرکس. لیکن ہم میٹرکس جب ان، ہم کیا کر رہے ہیں بنیادی طور پر دگنا ہے چھوٹے arrays کے سائز. ہم ایک عنصر کا ایک گروپ ہے arrays کے کہ ہم مؤثر طریقے سے دو عنصر arrays میں جمع. اور پھر ہم لوگ لے دو عنصر لڑیاں اور میں ان کے ساتھ جمع اسی طرح چار عنصر arrays کے، اور، اور اسی طرح، اور اسی طرح، ہم جب تک ایک N عنصر سرنی ہے. 

لیکن کتنے doublings یہ ن حاصل کرنے کے لئے لگتا ہے؟ واپس فون بک مثال کے طور پر کے بارے میں سوچو. کتنی بار ہم آنسو کرنے کی ضرورت ہے نصف میں فون بک، کتنے بار ہم نے فون بک فاڑ کرنے کی ضرورت ہے نصف میں، تو فون کی کتاب کے سائز دگنی؟ صرف ایک، ٹھیک ہے؟ 

تو کسی قسم کا ہے یہاں لوگارتمی عنصر. لیکن ہم اب بھی کرنے کے لئے کم از کم (ن) کے عناصر کے تمام پر نظر ڈالیں. ، بدترین حالات میں تو قسم ن لاگ ان ن میں چلتا ہے ضم. ہم پر نظر پڑے (ن) کے عناصر کے تمام، اور ہم نے ان کو یکجا کرنا ہے ایک دوسرے کے ساتھ لاگ ان ن اقدامات کے سیٹ میں. بہترین صورت میں، سرنی بالکل مطابق ہے. یہ بہت اچھا ہے. لیکن الگورتھم کی بنیاد پر ہم یہاں ہے ہم اب بھی تقسیم اور میٹرکس کے لئے ہے. اس معاملے میں اگرچہ، recombining غیر موثر کی طرح ہے. اس کی ضرورت نہیں ہے. لیکن ہم اب بھی کے ذریعے جانا ویسے بھی پورے عمل. 

بہترین صورت میں تو اور بدترین صورت میں، اس الگورتھم ن لاگ ان ن وقت میں چلتا ہے. ضم طرح یقینی طور پر تھوڑا سا trickier ہے دیگر اہم چھنٹائی یلگوردمز مقابلے ہم CS50 کے بارے میں بات ہے لیکن ہے کافی زیادہ طاقتور. 

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